Geek asks and answers

Solution for Big Theta Notation

I have a problem with a solution for big theta notation. I understand that the big O notation stands for the worst case and the top, while the Omega stands for the best case and the lower bound.

If I am given an algorithm that works in O (nlogn) time and Omega (n), how would I infer what Theta means? I begin to believe that there is a theta notation if and only if O and Omega are equal, is this true?

+3
source share
1 answer

Suppose your algorithm works in f(x).

f(x) = O(n*log(n))means that for a xsufficiently high constant c1 > 0, so f(x)there will always be less c1*n*log(n).

f(x) = Omega(n)means for xconstant high enough c2 > 0, so that f(x)will be more thanc2*n

So, now you know that from a certain point forward ( xlarge enough), your algorithm will work faster than c2*nslower than c1*n*log(n).

f(x) = Theta(g(x))means that for xlarge enough, there are some c3 > 0and c4 > 0, so that c3*g(x) <= f(x) <= c4*g(x)means it f(x)will only work with a constant factor faster or slower than g(x). So, f(x) = O(g(x))and f(x) = Omega(g(x)).

Conclusion: Only with O and Omega data, if they do not match, you cannot conclude what Theta is. If you have an algorithm, you can try and see if O can be selected too high, or Omega can be selected too low.

0
source

More articles:


All Articles