CODEWITHSUNDEEP
performance
EvaD
EvaD

Reputation: 15

How to arrive at log(n) running time of loop?

A loop whose variable is multiplied/divided by a constant factor at each iteration is considered to run in O(log(n)) time.

for example: 

for(i=1; i<=n;i*2){  
    --some O(1) operations ...  
}

How do I calculate or establish that this loop will run log(n) times?

I was previously explained that the factor by which the variable is divided/multiplied will be the base of the log.

I understand running times and their meanings, I just do not understand the math/reasoning that is required to arrive at this particular solution. How does one mathematically arrive at this solution from knowing that the loop runs from i=1 to i=n multiplying i by 2 each time?

(I am trying to understand this as a basis to understanding how increasing the variable by a constant power leads to a running time of log(log(n)).)

Upvotes: 1

Views: 664

Answers (2)

chiliNUT
chiliNUT

Reputation: 19573

This is how I make sense of it myself: Try to come up with a function f(x) to model your for loop, such that on the xth iteration of your for loop, your iterator i=f(x). For the simple case of for(i=0;i<n;i++) it is easy to see that for every 1 iteration, i goes up by one, so we can say that f(x)=x, on the xth iteration of the loop, i=x. On the 0th iteration i=0, on the first i=1, on the second i=2, and so on.

For the other case, for (i=1;i<n;i*=2), we need to come up with an f(x) that will model the fact that for every xth iteration, i is doubled. Successive doubling can be expressed as powers of 2, so let f(x)=2^x. On the 0th iteration, i=1, and 2^0=1. On the first, i=2, and 2^1=2, on the second, i=4, and 2^2=4, then i=8, 2^3=8, then i=16, and 2^4=16. So we can say that f(x)=2^x accurately models our loop.

To figure out how many steps the loop takes to complete to reach a certain n, solve the equation f(x)=n. Using an example of 16, ie for (i=1;i<16;i*=2), it becomes f(2^x)=16. log2(2^x=16) = x=4, which agrees with the fact that our loop completes in 4 iterations.

Upvotes: 2

yvs
yvs

Reputation: 517

According to the wikipedia:

the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

So lets assume we have a function T from input length N, T(N) means it takes T(N) seconds to run the algo on array of N. 

for(i=1; i<=n;i*2)

In case when we double the array size in your algorithm , we will get a recurrent formula: T(2*N)=T(N)+C , this means that if we double the array lenght it takes the same time as T(N) plus a constant time for operation.

There is a theory about how to solve such recurrences, but you can use simple approach with wolfram alpha solver, so , for this particular case we have the result

When you go in a loop via

for(i=1; i<=n;i+=3)

then T(N)=T(N-3)+C, which leads us to a linear time of execution.

Upvotes: 1

Related Questions