Using only definition of O(f(n)) prove that the following statements are false:

Question

Using only definition of O(f(n)) prove that the following statements are false:
a. ((6n^3)(log n) + 1)/(n^2 +1000)= O(log n)
b. max(nlog n,n(n-1)/2)=O(n^(3/2))
c. 3^n = O(2^n)
d. log n + n^(1/2) = O(log n)

Explanation / Answer

a) ((6n^3)(log n) + 1)/(n^2 +1000) > ((6n^3)(log n))/(n^2 +1000) = (6n)(log n)/(1 +(1000/n^2)) > (6nlogn)/ (1+ 1000). (6nlogn)/ (1+ 1000) > c x g(n). g(n) = logn 6n/1001 > c Since C is in terms of n, there will always be an n for any C such that f(n) > C x g(n) so therefore it is false. b) I solved this by calculating the actual big O and proving it wasn't the answer given. O Max = (O f(n) + O g(n)) = O (nlog n) + O ((n^2 - n)/ 2) = O (nlog n) + O (n^2) = O (n^2) != O (n^(3/2)) so false. c) 3^n > C x g(n). g(n) = 2^n. = 3^n/ 2^n > c = (3/2)^n > c = n > logC/ log(3/2) Since n is in terms of C, there will always be an n for any C such that f(n) > C x g(n) so therefore it is false. d) We can just say that since n^(1/2) grows faster than logn, for n > 1, for any c, there will always be an n such that (logn + n^1/2) > c x g(n). (logn + n^1/2) > c x g(n). (logn + n^1/2) > c x logn. You could also quickly calculate the true O like I did in b and use it to prove the given answer is wrong. Hope this helps, McMaster Comp Sci Unit represent.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.