2

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.

enter image description here

Improve this question
6
  • 2
    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.
    – Philip Kendall
    Commented Sep 24, 2019 at 6:08
  • 2
    @PhilipKendall: neither the first nor the second algorithms seems to return anything.
    – Doc Brown
    Commented Sep 24, 2019 at 7:57
  • 2
    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.
    – Doc Brown
    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)?
    – Freakup2
    Commented Sep 24, 2019 at 11:48

1 Answer 1

Reset to default
2

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

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.