I have just started learning Analysis of Algorithms and I came across these set of questions:
- Find witnesses c and m such that rn+1 = O(rn) for r>1
- Show that there are no witnesses for n2 = O(n)
- From 2, deduce no witnesses for 22n = O(2n)
So, I have tackled some as:
rn+1 ≤ rn+1
rn+1 ≤ r.rn
rn+1 ≤ (r+1).rn
Therefore, c = r + 1; m = 1
n2 ≤ n2
No value for c satisfies the above inequality, therefore no witnesses (??)
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.