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.
Gotcha
0
Newbie Poster
Recommended Answers
Jump to PostIf actual thinking fails, run through the code by hand for various values of N and notice a pattern.
All 4 Replies
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
If actual thinking fails, run through the code by hand for various values of N and notice a pattern.
leelee
11
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.
indianscorpion2
-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).
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
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).]
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.