Please support our Computer Science advertiser: Programming Forums
 |
•
•
Join Date: Sep 2005
Posts: 8
Reputation: 
Rep Power: 0
Solved Threads: 0
Newbie Poster
Need help finding the Big Oh. Instructions:
Find the Big Oh for the times of excecution of X: = x + 1. You should justify the answer:
I : = N
WHILE I >= 1 DO
BEGIN
FOR J : = 1 TO N DO
X : = X + 1
I = [I/2]
END
Thanks for any suggestions for solving it.
Find the Big Oh for the times of excecution of X: = x + 1. You should justify the answer:
I : = N
WHILE I >= 1 DO
BEGIN
FOR J : = 1 TO N DO
X : = X + 1
I = [I/2]
END
Thanks for any suggestions for solving it.
•
•
Join Date: Jun 2005
Location: Cambridge, MA
Posts: 1,374
Reputation:
Rep Power: 7
Solved Threads: 47
If actual thinking fails, run through the code by hand for various values of N and notice a pattern.
•
•
Join Date: Aug 2005
Posts: 76
Reputation:
Rep Power: 4
Solved Threads: 1
Junior Poster in Training
Gotcha: your post sounds exactly like a homework question. What a coincidence!
There are plenty of articles on the 'net describing big-O; a simple search will uncover them. Read some, think about your problem, then answer it. You'll be amazed at how satisfying it will be.
And, as an added bonus, you'll stand a better chance to pass your exams.
There are plenty of articles on the 'net describing big-O; a simple search will uncover them. Read some, think about your problem, then answer it. You'll be amazed at how satisfying it will be.
And, as an added bonus, you'll stand a better chance to pass your exams.
•
•
Join Date: May 2005
Posts: 80
Reputation:
Rep Power: 0
Solved Threads: 1
Junior Poster in Training
the time complexity for this algorithm is O(N*N)
since the outer loop is executed approaximately N/2 times and the inner loop is executed N times.
just multiply both.
you get (N*N)/2.
therefore, time complexity is O(N*N).
since the outer loop is executed approaximately N/2 times and the inner loop is executed N times.
just multiply both.
you get (N*N)/2.
therefore, time complexity is O(N*N).
•
•
Join Date: Jun 2005
Location: Cambridge, MA
Posts: 1,374
Reputation:
Rep Power: 7
Solved Threads: 47
Thanks for giving the wrong answer. The outer loop gets executed 1 + floor(log N) times.
The time complexity is not O(N*N).
[Edit: Erm, sorry for being snippy. Anyway, in the outer loop, I gets halved, not decremented, each time. The time complexity is O(N log N).]
The time complexity is not O(N*N).
[Edit: Erm, sorry for being snippy. Anyway, in the outer loop, I gets halved, not decremented, each time. The time complexity is O(N log N).]
|
Similar Threads
Other Threads in the Computer Science Forum
- Big theta (Computer Science)
- PHP vs ASP... the big ShOwdOwN (IT Professionals' Lounge)
- Motorola T720 Phone and Verizon Wireless (Gadgets and Gizmos)
- Finding the Big Oh for these Math.functions (Computer Science)
- C++ Templates (C++)
Other Threads in the Computer Science Forum
- Previous Thread: help pls :)
- Next Thread: problem with latest deadline scheduling
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
