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
13 Years
Discussion Span
Last Post by murschech

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.