Time complexity of a Nested While loop in a for loop

algorithm-analysisalgorithms

I'm trying to derive the simplified asymptotic running time in Theta() notation for the two nested loops below.

For i <-- 1 to n do
    j <-- 1
    while j*j <= i
        j = j+1

For i <-- 1 to n
    j <-- 2
    while j <= n
        j = j*j

I have been trying to solve this using the summation method but not really getting the right answer. The picture below shows my attempts at the problem, I was able to get (n^3/2) for the first algorithm, however, I wasn't sure how to proceed with the second algorithm.

Best Answer

First algorithm

We iterate n times in the outer loop. For every iteration i, the inner loop iterates from 1 to sqrt(i), so sqrt(i) times. So the total number of iterations is:

 n
 ∑ √i
i=1

I spare you and me the maths, but the result can be approximated by the integral of √n which is (2/3)*n^(3/2). For very big numbers, this is mainly driven by the strongest polynomial factor, so the the complexity is O(n^(3/2)).

Second alogrithm

If there's a typo and the while should be <= i

We iterate n times in the outer loop. For every iteration i, the inner loop iterates k times, where k is such that 2^k>i. k can easily be determined as log2(i) so log(i)/log(2).

so this time we have a total number of iteration of

 1      n
---- .  ∑ log(i)
log2   i=1

For the order of magnitude, we can ignore the constant coefficient and just look at the sum. Again, sparing you (and me!) the math, the sum is log(n!) which is approximated by nlog(n)

If there is no typo and it's really <= n

Then you perform n times the same inner loop which is made of log(n)/log(2) iterations, so here the number of iteration is

 1      n             1
---- .  ∑ log(n)  = ---- . n log(n)
log2   i=1          log2

So it's exactly O(nlog(n))

Related Solutions

Basic premise on counting sort. How is k related to to Big Oh

Your quote is saying that if the range of integers k is linearly proportional to the total number of elements in the collection n, then a counting sort will have a best-case and a worst-case time complexity of O(n), making it a very efficient sort in such a case.

Big Oh (and others in the Bachman-Landau family of notations) are just simplifications of the precise complexity of the function in any given case, used to illustrate the increasing value of the function as N grows large. In programming, Big Oh is usually used in the context of time complexity; for n values, a function f(n) will execute in a time on the order of g(n), and thus we say it has a Big Oh complexity of O(g(n)). However the mathematical construct of Big Oh isn't so limited. In this particular case, it is being used to refer to the general relationship between k and N as numbers.

Simply put, when k (the range of the values of an n-element collection) increases as n does on the order of O(n), then the counting sort will be efficient. This will be true if, say, the list contained all multiples of 4 between 1 and x (in which case k~=x, and n=x/4, meaning that k ~= 4n = O(n)). The condition k=O(n) would be false for, say, the set of all perfect squares from 1 to x² (in which case k=x² but n=x, so k = n² = O(n²)). In that case, k increases on the square (O(n²)) when N increases linearly (O(n)), so the counting sort would execute in the more complex time (which would be O(n²)), which would perform worse than some other sort implementation that ran in Theta(nlogn).

Time-complexity of nested for loop

You are summing up the numbers from 1 to n, incrementing the value by one each time. This is essentially the classic Gauss sumation which is:

sum(1 .. n) = (n * n-1)/2

This also happens to be the number of times through the loop.

(n^2 - n) / 2
(n^2)/2 - n/2

When representing Big O, only term with the highest power is used and constants are thrown away, and thus the answer is O(n²).

More about this particular problem can be read on CS.SE at Big O: Nested For Loop With Dependence