1. O(n)
2. O(n)
3. O(1)
4. 
Best: O(1) - first two elements are different
Worst: O(n) - all elements are the same
5. O(2^n).  There are ways to get tighter bounds, but think of each call generates two more recursive calls.