In each of the following situations, indicate whether f = O(g), or f = omega(g),
ID: 3637299 • Letter: I
Question
In each of the following situations, indicate whether f = O(g), or f =omega(g), or both (in which case
f = theta(g)).
(a) n - 100 ; n - 200
(b) n1=2 ; n2=3
(c) 100n + log n ; (n + (log n)) ^2
(d) nlog n ; 10n log10n
(e) log 2n ; log 3n
(f) 10 log n ; log^2 n
(g) n^1.01 ; n log 2n
(h) n2/log n ; n(log n)2
(i) n^0.1 ; (log n)10
(j) (log n)^log n ; n/log n
(k) n^0.5 ; (log n)^3
(l) n^0.5 ; 5^log2 n
(m) n^(2^n); 3^n
(n) 2^n ; 2^(n+1)
(o) n! ; 2^n
(p) (log n)^log n ; 2^((log2 n)^2)
(q) Summation from i=1 to i=n of i^k ; n^(k+1)
Explanation / Answer
f(n) g(n)
n 100 n 200 Big-Theta
n1/2 n2/3 Big-O
100n + log(n) n + log2(n) Big-Theta
n log(n) Big-Omega
n2 n log2(n) Big-Omega
n log(n) 10n log(10n) Big-Theta
log2(n) log(n3) Big-Omega
n1.01 n log2(n) Big-Omega
n0.1 log10(n) Big-Omega
n2 4log2(n) Big-Theta
2n n1000 Big-Omega
n2n 3n Big-O
2n 2n+1 Big-O
n! 2n Big-Omega
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.