Search code examples
runtimeanalysisbig-o

How do you find the runtime of loops that affect eachother?

I am not sure the technical term for these kinds of loops (if one even exists), so I will provide an example:

x=0
i = 1
while(i<n)
    for(j=1 to n/i)
        x = x + (i-j)
    i*=2
return(x)

In this example, the while loop is directly changing the number of times the for loop runs, which is throwing me off for some reason

Normally, I would go line by line and see how many times each line would run, but because the number of times changes, I tried doing a summation but got a little lost... What would be a step by step way to solve this type of problem?

The answer in the notes is O(n), but when I did this I got nlog(n)

Any help is appreciated, this is review for my final

Also, if you know of any good places to find practice problems of this sort, I would appreciate it!

Thank you

Solution

  • I think the analysis to this code is very similar to the one in this lecture to find the running time of the procedure of building a max heap. the straightforward analysis of it resulted in nlgn complexity but when analysed using summations it turned out to be n just like your problem.

    So back to your question, the outer loop runs enter image description here times and the inner runs n / i. But since i grows exponentially, we can use another variable j that that is increased once at a loop iteration so it can be used in summation and change the bounds according to the relation enter image description here.

    The summation is enter image description here The sum is a geometric sequence whose result is enter image description here so when n tends to infinity, it converges to a constant (2). Hence the summation is considered a constant factor and doesn't affect the asymptotic complexity of the code which is only O(n).