Solving the recurrence $T(n) = 7 T(n/2) +O(1)$

Question

I know how this works but I have the problem to "compute" the result. With $T(n) = O(1) n\geq2$

$T(n) = 7 T(n/2) + O(1)$

$T(n/2) = 7(n/4) + O(1)$
...

Now I have this when I see some pattern:

$7^3*T(n/8) +7^2 * O(1) + 7 * O(1) + O(1)$

Now I can say the term above is the same as :

$7^k * T(n/2^k) + 7k-1 * O(1)$

Now I say $n/2^k = 1$ and this $k= \log n$

$7\log n * T(1) + 7\log n-1 * O(1)$

Now at this point how shall I go on?

Answer 1

When $k=\log_2 n$ you should go from $7^k$ to $7^{\log_2 n}$ Now you can use the laws of exponents and logs to say $$7^{\log_2 n}=7^{\frac {\ln n}{\ln 2}}=\left(e^{\ln 7}\right)^{\frac {\ln n}{\ln 2}}=\left(e^{\ln n}\right)^{\frac {\ln 7}{\ln 2}}=n^{\frac {\ln 7}{\ln 2}}=n^{\log_2 7}\approx n^{2.8}$$