enter image description here

why option c is the answer ? And why not option B ?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W. Jun 18 '18 at 17:47

f will be called many times in this algorithm, as f(c0),f(c1),....

Since counter is reset to 0 after each call to f, we get that c0+c1+... <= n. Since f has a linear cost, the cumulative cost of all the calls to f is <= k c0 + k c1 + ... = k n for some constant k. Hence this cost is $O(n)$.

The rest of the program only adds $O(n)$ more operations, so we get $O(n)$ overall cost. Since the loop takes $\Omega(n)$ iterations, we also get $\Theta(n)$ overall cost.

| cite | improve this answer | | | | |
  • $\begingroup$ Thank u chi . Please can you suggest some books where i can find this type of tricky questions ? $\endgroup$ – Tatan Jun 18 '18 at 10:32
  • $\begingroup$ @user9605563 I don't know of any such books, I'm sorry. Perhaps you can google for this kind of algorithmic quizzes, or even some interview questions on algorithms. Usually, books on algorithms tend to give more deep exercises. $\endgroup$ – chi Jun 18 '18 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.