# 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

### Solution

(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.

### Comments

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

### Self-check

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.