Naïve algorithm

From Wikipedia, the free encyclopedia

A naïve algorithm is a very simple solution to a problem that has a very high time- or memory- complexity. It is meant to describe a suboptimal algorithm compared to a "clever" (non-naïve) algorithm. Naïve algorithms usually consume larger amounts of resources, but are simple to devise and implement.

An example of a naïve algorithm is bubble sort, which is only a few lines long and easy to understand, but has a Θ(n²) complexity. A more "clever" algorithm is quicksort, which, although being considerably more complicated than bubble sort, has a Θ(n log n) average complexity. For instance, sorting a list of 100 items with bubble sort requires 10000 iterations, while sorting the same list with quicksort requires approximately 110 iterations, making quicksort a much faster algorithm than bubble sort.

As demonstrated above, naïve algorithms are mostly used for prototyping purposes, as they are often not acceptable in production-level software products.