Time complexity of a Nested While loop in a for loop

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.

• Possible duplicate of What is O(...) and how do I calculate it?
– gnat
Commented Sep 24, 2019 at 5:55
• Are you aware your second algorithm returns the same value every time? That doesn't fundamentally affect the question but it makes me wonder if you've got a typo somewhere. Commented Sep 24, 2019 at 6:08
• @PhilipKendall: neither the first nor the second algorithms seems to return anything. Commented Sep 24, 2019 at 7:57
• This site is not for solving other peoples homework. But I will give you a hint how you can solve this by yourself: start with some examples for different values of n, and lookup the basic calculation rules for logarithms. Commented Sep 24, 2019 at 8:04
• Its just a practice problem that i'm having trouble with, i want to understand it first before going for my assignment @DocBrown. I am aware there is nothing returning, so the inside of each iteration should just be O(1) . I'm more interested in the Theta() of the nested loop it self. So for the second algorithm, i plugged in some n, but the loop will pretty much only run once. So J^2 <= n, which means j <= root(n)? Commented Sep 24, 2019 at 11:48

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))`