I've got to figure out the Big-O running time for this loop.

for (int k = 1; k < N; k = k*4){
    sequence of statements
}

I understand for the most part, except k = k*4 is giving me difficulty. My best guess would be O(n), but I am uncertain. Can anyone help?

CodePudding user response：

Try listing values of k to get an idea of how it will increase. 1 -> 4 -> 16 -> 64 -> ...

As we can see, k follows the pattern of 4^j, with j starting at 0 and increasing by one each time. So how many iterations of our for loop will pass before k >= N? Let's solve for j! 4^j >= N can also be written as j >= log base 4 of N. This means that for an input of size N we will have log base 4 of N iterations, which in terms of complexity is O(log(n)). Now obviously whatever is in the for loop will affect the final complexity, but hopefully this helps you with the outer loop.

CodePudding user response：

Here's another way to get your head round that outer loop.

Rewrite the loop as:

for(int i=0; pow(4,i)<N;   i){
    int k=pow(4,i); //Where pow is a nicely behaved int function....
}

Why does that help? Well it should be easier to see that iteration of the loop ends when pow(4,i)>=N and taking log of both sides gives Log(4)*i=Log(N).

That's based on the mathematical identity that Log(a^b)=log(a)*b you may recall... NB: ^ means 'to the power of' just here.

So i counts up in 1s until it equals or exceeds Log(N)/Log(4).

The asymptotic complexity O(Log(N)/Log(4)) but 1/Log(4) is a constant and we discard constant factors in Big-O and get O(Log(N)).

That makes sense because when N gets 4 times bigger we only need to do one more iteration because k gets 4 times bigger every iteration.

It's probably obvious if k=k*10 that we take log10(N) but because we ignore constant factors in big-O it all boils down to a logarithmic scaling rule (for that outer loop).