Big O - Recurrence

Question

I am given a function as follows:

GetMax(i,j)
1: IF i=j
2: Return A[i]
3: ELSE
4: max1 = GetMax(i, i+(j-i+1)/3-1)
5: max2 = GetMax(i+2*(j-i+1)/3,j)
6: Return max(max1, max2)

I need to figure out the time complexity.

First I said it is recursive as $$ T(n) = O(1) + 2T(\frac{n}{3}) $$$$ T(\frac{n}{3}) = O(1) + 2T(\frac{n}{3^2}) $$$$ T(\frac{n}{3^2}) = O(1) + 2T(\frac{n}{3^3}) $$ giving $$T(n) = O(1) + 2O(1) + 2^2O(1) + 2^3T(\frac{n}{3^3})$$ or as a general case

$$ T(n) =\mathcal{O}(1) \sum_{i=0}^{k-1} 2^i + 2^kT(\frac{n}{3^k}) $$

I know that $$T(1) = \mathcal{O}(1), n = 3^k, k = \log_3n$$

Now, here I am stuck, because in the previous examples we had the $$3^{\log_3n} = n$$ and this was easy to solve...

Any help?

Answer 1

$T(3^k) = \mathcal{O}(1)\cdot (2^k - 1) + T(1)\cdot 2^k = \mathcal{O}(1) \cdot 2^k. $

Thus $$ T(n) = \mathcal{O}(1)\cdot 2^{\log_3{n}} = \mathcal{O}(1)\cdot 2^{\frac{\ln{n}}{\ln{3}}} = \mathcal{O}(1)\cdot e^{\frac{\ln{n}}{\ln{3}}\cdot \ln{2}} = \mathcal{O}(1)\cdot \left(e^{\ln{n}}\right)^{\frac{\ln{2}}{\ln{3}}} = \mathcal{O}(n^{\frac{\ln{2}}{\ln{3}}})$$