Question

This is about analysis of algorithms:
Say, the running time of a problem is:

T(n) = 1, for n == 1
| T(n/3) + THETA(1), for n > 1
Now, this is THETA(log n) But, if I use Master Method, I evaluate to THETA(log n), using Case II How am I supposed to get the correct answer from master method?

Answer 1

Remember that: \[\large \log_bx=\frac{\log_ax}{\log_ab}=\left( \frac{1}{log_ab}\right) \log_ax=c\log_ax\]So the thing to remember here is that \(\Theta(\log n)\) can be applied to logarithms of all bases.

Answer 2

Yeah. thanks. I got it. The base doesn't matter. It's a constant factor, ignored in the asymptotic notations.