Member Avatar for Gotcha

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
  • 127 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by Rashakil Fol
Member Avatar for Rashakil Fol

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

Member Avatar for leelee

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.

Member Avatar for indianscorpion2

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

Member Avatar for Rashakil Fol

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.