In asymptotic notation, we use three symbols, O (omicron), Ohm (omega), and Thet
ID: 3827104 • Letter: I
Question
In asymptotic notation, we use three symbols, O (omicron), Ohm (omega), and Theta(theta). O is used when a function may give an upper bound on another function of interest; Ohm is used when we find a lower bound. When one function can provide an order-of-magnitude boundary on both sides of another function, we denote it as Theta. Here are the mathematical definitions of O, Ohm, and Theta: O(g(n)) {f(n): exist c, n_0 > 0: 0 lessthanorequalto f(n) lessthanorequalto cg(n) Forall n greaterthanorequalto n_0} Ohm(g(n)) {f(n): exist c, n_0 > 0: 0 lessthanorequalto cg(n) lessthanorequalto f(n) Forall n greaterthanorequalto n_0} Theta (g(n)) {f(n): exist c_1, c_2, n_0 > 0: 0 lessthanorequalto c_1g(n) lessthanorequalto f(n) lessthanorequalto c_2g(n) Forall n greaterthanorequalto n_0} Recall that the delta-equality symbol stands for definition, as in "is defined to be... a. State in words (or a mix of plain language words with at most a few symbols) an easy-to- read translation of what the above three definitions say: i. Big-Oh O(g(n)) ii. Big-Omega Ohm(g(n)) iii. Big-Theta Theta(g(n))Explanation / Answer
Big-Oh:
This is used for the worst case scenario of any algorithm. Some equation is given,
f(n) is our algorithm run time
g(n) is the time complexity
some constants say c(c>0) and n0, f(n) <= c g(n) for every n (n > n0).
g(n) = log n
statement is saying that f(n) is O(g(n)). Is (5 log n + 10) is O (log n)?
Big-Omega:
This is used for the best case scenario of any algorithm.
f(n) is our algorithm run time
g(n) is the time complexity
Some constants say c(c>0) and n0, c g(n) <= f(n) for every n (n > n0).
Big-Theta:
This is used for the average case scenario of any algorithm.
f(n) is our algorithm run time
g(n) is the time complexity
some constants say c1,c2,(c1,c2 >0) and n0, (c1 g(n)) is < f(n) is < (c2g(n)) for every n (n > n0).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.