Understanding the Time Complexity of Nested Loops in Algorithms

needhelp83 · Sep 1, 2009

Ok, I am brand new at this so I am kind of confused how to figure this out.

Code:

 i [tex]\leftarrow[/tex] n 
 while i >= 1     
  j [tex]\leftarrow[/tex] i 
  while j <= n 
   <body of the j loop>, needs (1) 
   j [tex]\leftarrow[/tex]j*2 
  end j while 
  i [tex]\leftarrow[/tex]i-1 
 end i while

I know that with nested loops that n goes to a power of 2, but it states that in my problem. What exactly am I missing and how do I show each step?

berkeman · Sep 2, 2009

needhelp83 said:
Ok, I am brand new at this so I am kind of confused how to figure this out.
Code:
 i [tex]\leftarrow[/tex] n 
 while i >= 1     
  j [tex]\leftarrow[/tex] i 
  while j <= n 
   <body of the j loop>, needs (1) 
   j [tex]\leftarrow[/tex]j*2 
  end j while 
  i [tex]\leftarrow[/tex]i-1 
 end i while
I know that with nested loops that n goes to a power of 2, but it states that in my problem. What exactly am I missing and how do I show each step?

n is an initializer, it would appear. So it does not change in value, does it? And the middle loop doesn't seem right. j gets initialized to n the first time, is left as n^2 after the firsts pass, and would appear to fail the comparison the 2nd time through? I must be missing something as well...

EDIT -- Oh, I see that j gets re-initialized before the 2nd comparison, so will not fail. In fact, it just keeps getting decremented until the outer loop comparison faiils, I guess.

JustSam · Sep 2, 2009

The body of the inner j loop is executed 1 + \lfloor \log_2 (n / i) \rfloor times for a given pass of the outer i loop. Now sum this over the different values of i from the outer loop.

needhelp83 · Sep 11, 2009

Alright, I didn't get this one quite right on the homework, but I am trying to figure out exactly how to solve this thing. The answer was n log n , but how do you total this up when going through the loop

Code:

i [tex]\leftarrow[/tex] n                                                                         1
   while i >= 1                                                                                       n
      j [tex]\leftarrow[/tex] i                                                                    1
         while j <= n                                                                                 n?
              <body of the j loop>, needs [tex]\Theta[/tex](1)                  [tex]\Theta[/tex](1) 
              j [tex]\leftarrow[/tex]j*2                                                         1
         end j while 
     i [tex]\leftarrow[/tex]i-1                                                                   1
end i while

Now when I total up I disregard so I left with n. Now I assume that the inner loop is log n, but I don't fully understand. Thanks for the reply justsam and berkeman, but further direction would be greatly appreciated

taifunbrowser · Sep 11, 2009

While I get what JustSam is saying, that's really not what O(N) is all about (keep the math out of it.).
"Summing up" the parts of an algorithm is, as far as I'm concerned, not how I solve these.

I rewrote what you put down so I could visualize it:

Code:

for(i = n; i>= 1; i--){    -LOOP B
   for(j = i; j <= n; j*=2){   -LOOP A
      <constant time steps>
   }
}

Alright, so we have linear-over-n many logarithmic-over-n loops. Multiply to get n*log(n).

Don't overanalyze O(N). These problems will introduce things (like the variable i above) just to waste your time. The goal is not to know exactly how many times a line will be executed given a certain N, the problem is to know how changing N will change the number of times the inner step is executed (O(N) tells you how Scalable your algorithm is)

So, think this: If I increase N, there will be linearly more outer loops, and logarithmically more inner runnings of the middle statement.

Consider these cases. If I gave you,

Code:

for(i = 0; i < n; i++){
   for(j = 0; j < n; j++){
      <statement>
   }
}

the runtime is obviously O(N^2)

Now try

Code:

for(i = 0; i < n; i++){
   for(j = i; j < n; j++){
      <statement>
   }
}

It's STILL O(N^2) man. we have linearly-over-n many linear-over-n inner loops. Multiply to get n*n.

Another example:

Code:

for(i = 1; i < n; i*=2){
  for(j = i; j <= n; j*=2){
    <statement>
  }
}

Go through it with me: We have logarithmic-in-n many logarithmic-in-n loops. Multiply to get O(N) = (log2(n))^2

Hurkyl · Sep 11, 2009

taifunbrowser said:

Alright, so we have linear-over-n many logarithmic-over-n loops. Multiply to get n*log(n).

In all fairness, that doesn't quite work: the inner loop varies with respect to i, and it is easy to construct examples where a simplistic multiplication give the wrong value, such as:

Code:

for(int i = 1; i < N; i *= 2) {
  for(int j = 0; j < i; ++j) {
    // Something
  }
}

which executes "Something" O(N) times, not O(N^2) times.

(keep the math out of it.).

How can you keep the math out of it?

The question we're trying to answer is already math!

In fact (assuming your intuition isn't simply flat out wrong), the way you are approaching this problem is most likely just appling the basic ideas of calculus! You intuitively recognize that most of the N times through the outer loop take nearly log(N)/log(2) steps and everything else is negligible, which heuristically justifies just multiplying the two.

But, for the record, it is very easy to turn it into a fully rigorous argument. For simplicity, let me define two functions:
A(N) = the time to run the whole algorithm
B(i,N) = the time to run the inner loop

First, we just replace the inner loop time with something that's always bigger, but still logarithmic:
We know B(i,N) < 1 + log(N) / log(2), and therefore
A(N) < N * (1 + log(N) / log(2)) = O(N log N)

Now, we isolate "most" of the iterations and find a logarithmic lower bound for those:
If i < N/2, then B(i,N) = log(N) / log(2), and therefore
A(N) > (N/2) log(N) / log(2) = O(N log N)

And we put it together to get A(N) = O(N log N)

Redbelly98 · Sep 11, 2009

needhelp83 said:

Now I assume that the inner loop is log n, but I don't fully understand.

It would be log(n), base 2, if j were initialized to 1 instead of i each time. Are you sure that is not the case?

EDIT: just read Hurkyl's last post more carefully ... looks like a good argument to me.

taifunbrowser · Sep 11, 2009

@hurkyl: Ah, that makes sense.

Minor correction, do you mean

Code:
for(int i = 1; i < N; i *= 2) {
  for(int j = 0; j < i; ++j) {
    // Something
  }
}
which executes "Something" O(N) times, not O(N*Log(N)) times.

Well, I was curious why flipping the inner with the outer loop mattered so much, and I was really surprised. Here are some graphs:

http://taif09.exofire.net/report/ONdata/

So yes, it looks like every situation with nested loops is a little different. I still don't think the inclusion of i / a "middle" variable is really the important thing, but I guess I don't have any basis for this assumption. Neat, though.

needhelp83 · Sep 12, 2009

Thanks for all the help.

Wow, this seems to be a very interesting problem. So with looking at the arguments I am gathering the inner loop is a log n while the outer loop remains n and you multiply together.

Understanding the Time Complexity of Nested Loops in Algorithms

Discussion Overview

Discussion Character

Main Points Raised

Areas of Agreement / Disagreement

Contextual Notes

Who May Find This Useful

Similar threads

Bending Stress and Shear Stress

Four L-shaped members: Mechanical Analysis Problem

Engineering Joint and Marginal Distributions of a Randomly Selected Test Answer

Engineering Full bridge circuit with inductor and resistor

Engineering AM-AM and AM-PM graph generation in LTSpice

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Insights What Exactly is Dirac’s Delta Function? - Insight