I have just started learning Analysis of Algorithms and I came across these set of questions:

  1. Find witnesses c and m such that rn+1 = O(rn) for r>1
  2. Show that there are no witnesses for n2 = O(n)
  3. From 2, deduce no witnesses for 22n = O(2n)

So, I have tackled some as:

  1. rn+1 ≤ rn+1
    rn+1 ≤ r.rn
    rn+1 ≤ (r+1).rn
    Therefore, c = r + 1; m = 1

  2. n2 ≤ n2
    No value for c satisfies the above inequality, therefore no witnesses (??)

  3. 22n ≤ 22n
    No value for c satisfies the above inequality, therefore no witnesses (??)

I am not sure how to go about the last 2. Can anyone please tell me whether what I have done is correct?


  • 1
    $\begingroup$ e discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ Feb 25, 2017 at 16:30

1 Answer 1


Part 1 looks OK.

For part 2, to show no witnesses exist, you have to proceed by contradiction. Assume witnesses $c,m$ exist, so we have $n^2 \leq cn$ for all $n\geq m$. Now, to reach a contradiction, find at least one value of $n \geq m$ for which $n^2 > cn$. The value for $n$ can be defined in terms of $c,m$. It shouldn't be too hard to find one.

For part 3, the text suggests to use 2. That is, to prove that if we had (by contradiction) witnesses for 3, we could derive from them some witnesses for 2.

(Honestly, to me this way sounds harder than simply tackling 3 on its own, without exploiting 2. Maybe you were introduced to some theorem which can apply here to shorten the exercise? I have no idea.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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