For each pair of expressions (A,B) below, indicate whether A is O, o, omega, w,
ID: 3541653 • Letter: F
Question
For each pair of expressions (A,B) below, indicate whether A is O, o, omega, w, or theta of B. Note that zero, one or more of these relations may hold for a given pair; list all correct ones.
To get any credit explain your answers breifly.
Link to the picture of the problem set: (chegg image isnt working):
http://i.imgur.com/Epl2tyY.png
For each pair of expressions (A,B) below, indicate whether A is O, o, omega, w, or theta of B. Note that zero, one or more of these relations may hold for a given pair; list all correct ones. To get any credit explain your answers briefly.Explanation / Answer
a) A is O(B), o(B); B is omega(A), w(A)
This is because for every choice of a constant k > 0, you can find a constant a such that the inequality A(x) < k B(x) holds for all x > a. So, A is o(B) and O(B).
If A is O(B), B is omega(A). If A is o(B), B is w(A)
Similarly:
b) A is O(B), o(B); B is omega(A), w(A)
c) No relationship!
This is because B is always in the range [1/n, n]. A is monotonically (constantly) increasing.
So, no constant k can be found so that inequality A(x) < k B(x) holds for all x > a, or vice-versa.
d) A is O(B), o(B); B is omega(A), w(A)
B is a much faster growing function as the base is 100, whila base for A is 10.
e) A is theta(B), B is theta(A), A is O(B), B is O(A)
A and B are the same functions. Take log on both the sides, and you can see that both become (log n)^2
f) A is theta(B), B is theta(A), A is O(B), B is O(A)
order of complexity of n! = n^n; Thus O(log(n!)) = O (n log n). Both the functions reduce to the same function.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.