What is a "naive" algorithm, and what is a "closed - form" solution?

algorithm code-analysis
user559142 picture user559142 · Apr 18, 2011 · Viewed 26.3k times · Source

I have a few questions regarding the semantics of terminology used when describing algorithms.

Firstly, what is meant by a 'naive' algorithm? How does this differ from other solutions to a given problem? What other forms can solutions take?

Secondly, I have heard much reference to having a 'closed - form' solution. I have no idea what this means either - but often it appears when trying to solve recurrence relations...

Thanks for your time

Answer

st0le picture st0le · Apr 18, 2011

A Naive algorithm is usually the most obvious solution when one is asked a problem. It may not be a smart algorithm but will probably get the job done (...eventually.)

Eg. Trying to search for an element in a sorted array. A Naive algorithm would be to use a Linear Search. A Not-So Naive Solution would be to use the Binary Search.

A better example, would be in case of substring search Naive Algorithm is far less efficient than Boyer–Moore or Knuth–Morris–Pratt Algorithm

A Closed Form Solution is a simple Solution that works instantly without any loops,functions etc..

Eg: Iterative Algorithm for sum of integer from 1 to n

s= 0
for i in 1 to n
s = s + i
end for
print s

Closed Form (for the same problem)

s = n * (n + 1 ) /2

Related questions

Whats the difference between NP and co-NP

I know their complete counterparts mean that NP - complete is the hardest in the NP problems and co-NP-complete means the hardest in co-NP problems but whats the difference between the two? My textbook said "The yes and no are …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More