How to solve the recurrence for Heapify with repeated backward substitution?

Question

So I'm trying to solve the recurrence

So I have:

T(n) <= T(2n/3) + O(1)

We can write:

<= T(2n/3) + O(1)

<= T(4n/9) + 2O(1) 

...

<= T((2/3)^i * n) + i*O(1)

So if we solve for i

(2/3)^i * n = 1
(2/3)^i = (1/n)
i = log_(2/3)(1/n)

Which ten yields:

T((2/3)^(log_(2/3)(1/n)) + log_(2/3)(1/n)*O(1)

I.e.

T(1) + log_(2/3)(1/n)

So the time complexity would be: O(log_(2/3)(1/n))


Which could be also written as: O(-log_(2/3)(n))

Well, now it's negative. Is it still in O(log n)?

Is this correct? If yes, how can I derive O(log n) from O(log_(2/3)(1/n))?

If not, how would you do it?

I tried to solve it myself and wrote down my process in the question, so people can also just correct me if I was mistaken or add stuff to it.

Answer 1

It seems I did it correctly, here the idea: Apparently this is a log rule.

log_(a/b) (1/c) = log_(b/a) (c), only if (a/b) < 1.

Which means:

log(2/3) (1/n) = log_(3/2) (n).

And log_(3/2) (n) is in O(log n).