# Find witnesses (or not)

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?

Thanks.

• 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. Feb 25, 2017 at 16:30

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.