1. (20 points) (a) (5 points) logn - O(g(n)) for which of the following definiti
ID: 3584923 • Letter: 1
Question
1. (20 points) (a) (5 points) logn - O(g(n)) for which of the following definitions of g(n)? Circle all that apply: ·g(n) = 1 ·g(n) log n + 247 o g(n)nlogn ·g(n) = log n » None of the above (b) (5 points) logn-(g(n)) for which of the following definitions of g(n)? Circle all that apply: . g(n) ·g(n) log n + 247 o g(n)nlogn ·g(n) = log n » None of the above Read the following questions carefully: they are phrased different from the above. (c) (5 points) f(n)e(n) for which of the following definitions of f (n)? Circle all that apply: · f(n)=0 · f (n)= 247 f(n)= 247n ·f(n)=247n+ 131 » None of the above (d) (5 points) f(n) (0) for which of the following definitions of f (n)? Circle all that apply: · f(n)=0 · f (n)= 247 f(n)= 247n ·f(n)=247n+ 131 » None of the aboveExplanation / Answer
(a) O(g(n))=logn
Definition: If O(g(n)) = f(n), then it applies g(n)>=f(n)
Therefore,
(i) g(n)=1,
O(1) = logn
Is not True, as 1 is not always greater than log n.
(ii) g(n)= log n+247
It is true, as for relatively large value of n log n+247>=log n.
(iii) g(n) = n
It is not true as n is not always greater than log n
(iv) g(n) = nlog n
It is not true, as nlog n is not greater than n always
(v) g(n)= n^2log n
It is also not true as n^2log n is not greater than n always.
(b) Definition: (n) : For every n, f(n)>=g(n)
(i) g(n) = log n
Therefore, (1) = log n
It is false as logn is not always greater than equal to 1.
(ii) g(n) = log n+247
It is true as for larger values of n, n is nearly equal to log n + 247.
(iii) g(n)= n
It is false, as log n is not greater than n.
(iv) g(n)= nlogn
It is false as logn is not greater than nlog n.
(v) g(n) = n^2log n
It is also false, as n^2log n is not greater than log n always.
(c) Definition (n): For every n, f(n) = g(n).
f(n) = (n) (given)
(i) f(n) = 0
It is false, as for large values of n, (n) may not be zero.
(ii) f(n) = 247
It is false, as for large values of n, (n) may not be 247.
(iii) f(n) = n/247
It is true as for large values of n, n/247 ~ n.
(iv) f(n) = 247n
It is true as for large values of n, n247 ~ n.
(v) f(n) = 247n +131
It is true as for large values of n, n247+131 ~ n.
(d) f(n) = (0)
(i) f(n) = 0
It is true as (0)=0.
(ii) f(n) = 247
It is true as both are nearly constants.
(iv) f(n) =n/247
It is false as for relatively large values of n,n/247 may not be equal to 0.
(v) f(n)= 247n
It is false as for larger values of n, 247n may not be equal to 0.
(vi) f(n) = 247n +131
It is false as for larger values of n, 247n +131 may not be equal to 0.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.