944,144 Members | Top Members by Rank

Ad:
Nov 28th, 2004
0

Big O Notations...Need Help

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

A nested loop followed by a non-nested loop:

1.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
}
}
Similar Threads
Reputation Points: 7
Solved Threads: 1
Junior Poster in Training
harshchandra is offline Offline
68 posts
since Nov 2004
Administrator
Staff Writer
Reputation Points: 1422
Solved Threads: 163
The Queen of DaniWeb
cscgal is offline Offline
13,646 posts
since Feb 2002
Jan 16th, 2005
0

Re: Big O Notations...Need Help

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.
Reputation Points: 21
Solved Threads: 1
Junior Poster in Training
murschech is offline Offline
60 posts
since Dec 2004
Jan 16th, 2005
0

Re: Big O Notations...Need Help

>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.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Jan 18th, 2005
0

Re: Big O Notations...Need Help

The k loop runs N times, not one time.
Reputation Points: 11
Solved Threads: 8
Posting Whiz in Training
Real-tiner is offline Offline
207 posts
since Dec 2004
Jan 18th, 2005
0

Re: Big O Notations...Need Help

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.
Reputation Points: 21
Solved Threads: 1
Junior Poster in Training
murschech is offline Offline
60 posts
since Dec 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Computer Science Forum Timeline: Linear Algebra crisis
Next Thread in Computer Science Forum Timeline: online camera





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC