Understanding the Time Complexity of Nested Loops in Algorithms

AI Thread Summary
The discussion focuses on understanding the time complexity of nested loops in algorithms, specifically analyzing a code snippet with an outer loop decrementing from n and an inner loop doubling j until it exceeds n. Participants clarify that the inner loop executes approximately log(n) times for each iteration of the outer loop, leading to a total complexity of O(n log n). There is confusion about the initialization and behavior of the variables, but it is established that the outer loop runs n times while the inner loop runs log(n) times, thus confirming the overall complexity. The conversation emphasizes the importance of understanding how nested loops interact and the significance of variable initialization in determining time complexity. Ultimately, the conclusion is that the algorithm's efficiency can be expressed as O(n log n).
needhelp83
Messages
193
Reaction score
0
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?
 
Physics news on Phys.org
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.
 
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.
 
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
 
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
 
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? :confused: 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)
 
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.
 
@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.
 
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.
 

Similar threads

Evaluate the complexity of this graph coloring algorithm
Replies
1
Views
2K
Runtime of the line where a recursive call happens = ?
Replies
10
Views
2K
Comp Sci Complexity for generating strings of length k from CNF grammar
Replies
3
Views
1K
Comp Sci Learn How to Write Pseudocode: Questions Answered!
Replies
15
Views
5K
Engineering Intro to Power Systems: Calculating Power
Replies
7
Views
2K
Comp Sci Make an array with this series (java challenge)
Replies
5
Views
2K
Populating a 1001x101 2D array in MATLAB
Replies
3
Views
1K
Comp Sci Galaxy simulation with the velocity Verlet algorithm
Replies
3
Views
2K
Matlab Function for Composite Simpson
Replies
3
Views
1K
Comp Sci I need a solved numerical example on genetic algorithm for 1 iteration
Replies
11
Views
2K

Hot Threads

Recent Insights

Back
Top