Algorithms problem 1

Here is the code again, for reference:

01 Gnarly (a[1],..., a[n]:  array of integers) 
02     if (n = 1) return true
03     else if (n = 2)
04         if (a[1] = a[2]) return true
05         else return false 
06     else if (Gnarly(a[1],...,a[n-1]) and Gnarly(a[2],...,a[n])) return true 
07     else return false 


(a) All the values in the input array must be equal. The base cases (lines 02-05) check that that is true for very small arrays. If the array contains three or more elements, then verifying that all the elements are equal when you remove each of two different elements (line 06) forces all the elements to be equal in the whole array.

(b) Here is a recursive definition for the running time of Gnarly on an input of length n.

\( \begin{eqnarray*} T(1) &=& c \\ T(2) &=& d \\ T(n) &=& 2T(n-1) + p \end{eqnarray*} \)

(c) Gnarly takes \(\Theta(2^n)\) time. This recursive definition is basically the same as that for the Towers of Hanoi solver. That is, each node in the recursion tree contains the same value p, except for the leaf nodes which contain c or d. But there are \(O(2^n)\) nodes in the tree.


Yes, this is a really stupid way to determine if all elements are equal. The same answer can be returned in O(n) time.


Does your recursive definition have a base case?

The three constants c, d, and p should be different (though obviously you could give them all sorts of different names). So this is technically wrong (though not everyone will mark it as an error):

\( \begin{eqnarray*} T(1) &=& T(2) = c \\ T(n) &=& 2T(n-1) + c \end{eqnarray*} \)

However, the only thing that really matters about these terms is that they don't depend on the input size n, i.e. that they are constant time. The conventional shorthand for this is O(1). So another reasonable way to write this definition would be:

\( \begin{eqnarray*} T(1) &=& O(1) \\ T(2) &=& O(1) \\ T(n) &=& 2T(n-1) + O(1) \end{eqnarray*} \)

There's a variety of reasonable ways to justify the conclusion that it's \(O(2^n)\). Appealing to an isomorphic standard example (as above) is helpful to the reader but this works only if they are already familiar with that example. The above solution gave a very quick sketch of the recursion tree. You could supply a more careful recursion tree analysis or unroll the definition, especially when writing for a very picky audience.