Naïve algorithm

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (May 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

A naïve algorithm is a very simple solution to a problem. It is meant to describe a suboptimal algorithm compared to a "clever" (but less simple) algorithm. Naïve algorithms usually consume larger amounts of resources (time, space, memory accesses, ...), 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²) time 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 10,000 iterations, while sorting the same list with quicksort requires approximately 1000 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.