3

Compute the complexity of the following Algorithm?

I have the following code snippet:

i = 1;
while (i < n + 1) {
    j = 1;
    while (j < n + 1) {
        j = j * 2;
    }
    i = i + 1;
}

plz explain it in detail

I want to know the the steps to solve the problem so I can solve such problems

Jarod42
  • 203,559
  • 14
  • 181
  • 302
sangeen
  • 304
  • 2
  • 3
  • 14

5 Answers5

8

Since j grows exponentially, the inner loop takes O(log(n)).

Since i grows linearly, the outer loop takes O(n).

Hence the overall complexity is O(n*log(n)).

barak manos
  • 29,648
  • 10
  • 62
  • 114
  • 1
    +1 for succinct, correct answer and proper use of math-words. – Conduit Aug 19 '14 at 16:17
  • @Conduit: Thanks :) ... What does *succinct* mean by the way? – barak manos Aug 19 '14 at 16:18
  • Thank you so much Barak manos , but go in more detail :p – sangeen Aug 19 '14 at 16:19
  • 2
    @sangeen: More details?? It's kinda hard considering the sheer size of your code... – barak manos Aug 19 '14 at 16:21
  • 1
    @sangeen: Sorry, but I don't think that this website is meant for people to provide other people with answers sufficient for full marks given to them by their teachers. I provided you with a basic answer (plus an up-vote to your question, by the way), and I think it is reasonable enough for you to do the rest of the job here. – barak manos Aug 19 '14 at 16:26
  • @barakmanos very clear and short/to-the-point – Conduit Aug 19 '14 at 16:33
  • @Conduit: Right, well, that's exactly what I tried to explain to OP in one of the comments above :) – barak manos Aug 19 '14 at 16:34
  • @barakmanos Weren't you aware that we are a homework machine? Question in, A+ out, hehe. – Conduit Aug 19 '14 at 16:35
  • @Conduit: Yeah, well... I don't really have a problem with that to be honest, but in this case, asking for any more details within the answer feels a bit like... kinda greedy if you know what I mean... – barak manos Aug 19 '14 at 16:39
4
i = 1;
while(i < n + 1){
    j = 1;
    While(j < n + 1){
        j = j * 2:
    }

    i = i + 1;
}

outer loop takes O(n) since it increments by constant.

i = 1;
while(i < n + 1){

    i = i + 1;
}

inner loop : j = 1, 2, 4, 8, 16, ...., 2^k
j = 2^k (k >= 0) when will j stops ?
when j == n,
log(2^k) = log(n)
=> k * lg(2) = lg(n) ..... so k = lg(n). 

While(j < n + 1){

        j = j * 2;
}

so total O(n * lg(n))

2

You can simply understand outer-loop(with i) because it loops exactly n times. (1, 2, 3, ..., n). But inner-loop(j) is little difficult to understand.

Let's assume that n is 8. How much it loops? Starting with j = 1, it will be increased as exponentially : 1, 2, 4, 8. When j is over 8, loop will be terminated. It loops exactly 4 times. Then we can think general-form of this problem...

Think of that sequence 1, 2, 4, 8, .... If n is 2^k (k is non-negative integer), inner-loop will take k+1 times. (Because 2^(loop-1) = 2^k) Due to the assumption : n = 2^k, we can say that k = lg(n). So we can say inner-loop takes lg(n)+1 times.

When n is not exactly fit to 2^k, it takes one more time. ([lg(n)]+1) It's not a big deal with complexity though it has floor function. You can ingonre it this time.

So the total costs will be like this : n*(lg(n)+1). If you are familiar with Big-O notation, it can be expressed as : O(n lg n).

Phryxia
  • 139
  • 9
2

This one is similar to the following code :

for( int i = 1;i < n+1 ; i++){ // this loop runs n times
    for(int j = 1 ; j<n+1 ; j=j*2){// this loop runs log_2(n)(log base 2 because it grows exponentially with 2)
      //body
    }
}

Hence in Big-Oh notation it is O(n)*O(logn) ; i.e, O(n*logn)

Shankar
  • 417
  • 1
  • 6
  • 17
0

You can proceed like the following:

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32