Q3

You want to show that the solution of T(n) = T(n/8) + 15 is

O(lg n), using the substitution method. You may assume that

n is a perfect positive power of 8. If you plug in recursively, any

large C' value will work within the standard inductive proof, but

very small C' values will not work.

The smallest value that works within the proof is