hi everyone
dus u plzz tell me the complexities of following codes.
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
}
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
}
}
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.
>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.
The k loop runs N times, not one time.
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.
