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

Question

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 1

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 

Answer 2

Naive algorithm is a very simple algorithm, one with very simple rules. Sometimes the first one that comes to mind. It may be stupid and very slow, it may not even solve the problem. It may sometimes be the best possible. Here's an example of a problem and "naive" algorithms:

Problem: You are in a (2-dimensional) maze. Find your way out. (meaning: to a spot with an "EXIT" sign :)

Naive algorithm 1: Start walking and choose the right one in every intersection you meet (until you find "EXIT").

Naive algorithm 2: Start walking and choose a random one in every intersection you meet (until you find "EXIT").

Algorithm 1 will not even get you out of some mazes!

Algorithm 2 will get you out of all mazes (although this is rather hard to prove).