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.

4
Contributors
4
Replies
5
Views
13 Years
Discussion Span
Last Post by Rashakil Fol

If actual thinking fails, run through the code by hand for various values of N and notice a pattern.

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.

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).

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).]

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.