1.In the definition of Big-O, why is the \"for N >= n0\" needed? 2. If f1(N) = 2
ID: 3541966 • Letter: 1
Question
1.In the definition of Big-O, why is the "for N >= n0" needed? 2. If f1(N) = 2N and f2(N) = 3N, why are they both O(N), since 3N is larger than 2N for N>=1? 3. For f1(N) = 2N and f2(N) = 3N, what happens to the result in each case when N is doubled? Repeat using f1(N) = N*N and f2(N) = 2*N*N. What happens this time? 4. Since Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analysis? 5. Which grows faster, 2^n or n! ? Why? 6. Give the Big-O notation for the following expressions: a. 4n^5 + 3n^2 - 2 b. 5^n - n^2 + 19 c. (3/5)*n d. 3n * log(n) + 11 e. [n(n+1)/2 + n] / 2
Explanation / Answer
1. The "for N>N0" is needed because the graphs of the algorithms can be abnormal or ambiguous but after N0 the bigger function should always be above the smaller one.
2. 3N=2N=O(N)
Let O(N)=k. => k can be selected and N0 can correspondingly found out.=>K is arbitrary and hence,
for N>=1 , if k>3 , 3N<kN => 3N=2N=O(N)
3.F1(n)=2n F2(n)=3n. If n is doubled, F1 and F2 are both doubled as they are linear and bound in O(n).
F1(n)=n*n and F2(n)=2*n*n. If n is doubled, F1 and F2 are both quadrapled as they are quadratic and bound in O(n^2).
4.Big-O notation is used to calculate the worst case runtime of an algorithm. We get the runtime of a piece of code by calculating the statements and loops in the code. Hence, we get a function in T.
We bind or limit this function with a function bigger than this original function and hence, we get the worst time complexity.
5. n! grows faster than 2^n because in 2^n as n increases we multiply by 2 and in n! we multiply by n . If n>2 , we are basically multiplying by a number greater than 2.
6.
a) O(n^5)
b)O(5^n)
c)O(n)
d)O(nlogn)
e)O(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.