algorithm - Time Complexity of a loop that integer divides the loop counter by a constant

Question

I'm trying to calculate the time complexity of a simple algorithm in big O notation, but one part of it is seriously boggling my mind. Here is a simplified version of the algorithm:

int a=n
while(a>0)
{
//for loop with time complexity n^3
a = a/8
}

In this instance, it's integer division, so the while loop will terminate after a's value drops below 8. I'm not sure how to express this in terms of n. I'd also like to know how to tackle future calculations like this, where the number of loops isn't too easy to define.

Answer 1

I find it easier to do it the other way around in cases like this. What is the opposite of what you're doing (even approximately)? Something like:

for (a = 1; a <= n; a = a * 8)
{
    ...
}

Now, we've changed the while to a for, which has a fixed number of steps, and decrementation to incrementation, which can be easier to work with.

we have:

1, 8, 8^2, ..., 8^k <= n

8^k <= n | apply logarithm

log (8^k) <= log n

k log 8 <= log n

=> k = O(log n)

So your while loop executes O(log n) times. If you have something that is O(n^3) inside, then your entire sequence will be O(n^3 log n).