Proof exponential runtime by induction

Question

I have a problem showing with induction that the given function

foo :: [Int] -> Int
foo    []  = 0
foo (x:xs) = max (max x (foo xs)) (max (-x) (foo xs))

which returns the max absolute value of a given list of Int's , has a runtime of O(2^n).

I got so far by now:

t(0) = 1 and t(n>1)= 2 * t(n-1) + 4 where t shows the sum of calls of foo and max for a list of n elements.

Base Case:            n = 0 => t(0) = 1 <= c * 2^0, for c >= 1
Induction Hypothesis: t(n) <= c * 2^n
Induction Step:       n -> n+1
                   => t(n+1) <= c * 2^{n+1}
                  <=> 2 * t(n) + 4 <= c * 2^{n+1} | Induction Hypothesis
                  <=> 2 * c * 2^n + 4 <= c * 2^{n+1}
                  <=> c * 2^{n+1} + 4 <= c * 2^{n+1}

which is obviously wrong and I don't know how to fix that issue.

Thanks in advance!

Answer 1

Let's try to prove a tighter bound, like

t(n) <= c*2^n - k        (*)

for some constants c and k.

Assuming (*) holds by induction hypothesis, we get

t(n+1) 
= { recursive definition }
2*t(n) + 4
<= { induction hypothesis }
2*(c*2^n - k) + 4
<= { math }
c*2^(n+1) - 2k + 4
<= { ???? }
c*2^(n+1) - k

Now, we only need to choose k so that we can actually justify the last step, but that's easy.

Note that we also need to check the base case t(0), and choose c.

I'll leave the rest to you.