0

hi everyone
dus u plzz tell me the complexities of following codes.

  1. A nested loop followed by a non-nested loop:

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            sequence of statements
        }
    }
    for (k = 0; k < N; k++) {
        sequence of statements
    }
    
  2. A nested loop in which the number of times the inner loop executes depends on the value of the outer loop index:

    for (i = 0; i < N; i++) {
        for (j = i; j < N; j++) {
            sequence of statements
        }
    }
    

Edited by Dani: Formatting fixed

5
Contributors
5
Replies
6
Views
12 Years
Discussion Span
Last Post by murschech
0

In the first case the outer loop (i loop) repeats N times and for each repeat of the outer loop (i loop) the inner loop repeats N times. As you wrote this program, the k loop runs once, having nothing to do with i or j, so whatever the loop does, it does it N^2 + N times and this is O(N^2). In the second case for i = 0 the j loop runs N times, for i = 1 it runs N-1 times, etc. So the number of times the loop does its stuff is 1+2+...+N, and this sum is N*(N+1)/2 = N^2 /2 + N/2. This is also O(N^2), so both programs do O(N^2) repeats of whatever they do.

Perhaps your question is why N^2 + N is O(N^2) and also N^2/2 + N/2 is O(N). The answer is that a function of N is called O(N^2) when that function devided by N^2 approaches a non-zero limit as N approaches infinity.

I guess I just did your homework for you. That's bad.

0

>I guess I just did your homework for you. That's bad.
That's not an edit, so you knew that you did his homework and you knew that it was bad before you clicked submit. So were you trying to show off? If so, you failed miserably.

0

The loop runs once but, as you say, it does whatever it does N times. That's where the N in N^2+N comes from. By contrast, the j loop runs once for each value of i, therefore the j loop runs N times. Each of the N times it runs it does whatever it does N times. That's where the N^2 comes from.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.