Running time of a function

Today I will analyze a problem from GATE 2015 paper 1, that is asking for running time analysis of a C program. Here is the question (click on the image to see it properly): 

NOTE: This post is a part of a series on GATE previous year question analysis. You can explore other posts from this series using the navigation bar at the top.

What we need to understand

Since this is a small enough C program, we can just analyze the running time of each statement and combine their running times to get the final answer. What we need to understand is:

1. When two statements are executed one after the other in a program, their running time gets added. 
2. When statements are executed inside a for loop that loops n times, we need to multiply the running time of each statement by n.

Solution

Note that apart from the for loop statements themselves, each of the statements in the program are just simple imperative statements that need constant time to execute. So it just boils down to finding out the number of times each for loop iterates for a given n to find out the running time. There are three fors in the program, i-for, j-for and k-for. j-for and k-for are one after the other in the i-for. So the running time of this program is going to be 

i-for * (j-for + k-for) 

i-for

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

Nothing can be simpler than this. The i-for is looping numbers from 1 to n, taking O(n) time. 

j-for 

for (j=n;j>1;j=j/2) 

This is where it gets tricky. The running time of j-for is not obvious, but can be easily figured out. Notice that the loop is halving the value of n in every iteration. The question is - How many times can we half a value of a number before it become less than 1? Recall that halving a number is the inverse of doubling a number. So if we were to double a number n times, we would get 2^n. Since we are doing the opposite, we get logn. So for any number, we can only half it logn times, before it reaches 1. Take a few numerical examples to understand this. It is very important you get this concept. 

k-for 

for (k=1; k<p;k=k*2) 

Here p is the number of times the previous for loop runs, i.e. log n. In this for loop, we are doubling the value of k till it reaches p. Assume that this loop runs x times. 

Thus 
p = 2^x

Taking log of both sides we get: 

logp = x

But 
p = logn 

therefore 
x = log(logn) 

Hence the k-for runs for log(logn) times. 

Final Answer

Combining everything from above we get: 

Total running time = i-for * (j-for + k-for) 

             = O(n) * ( O(logn) + O(log(logn))

Since O(logn) > O(log(logn)):

O(logn) + O(log(logn)) = O(logn)

Hence the total running time = O(n) * O(logn) 

                    = O(n*logn)