Solving for Big Theta Notation
I'm having an issue solving for big theta notation. I understand that big O notation denotes the worst case and upperbound while Omega notation denotes the best case and lower bound.
If I'm given an algorithm that runs in O(nlogn) time and Omega(n), how would I infer what Theta equals? I'm beginning to assume that there exists a theta notation if and only if O and Omega are equal, is this true?
Assume your algorithm runs in f(x) .
f(x) = O(n*log(n)) means that for x high enough there is some constant c1 > 0 so that f(x) will always be smaller than c1*n*log(n) . f(x) = Omega(n) means that for x high enough there is some constant c2 > 0 so that f(x) will be bigger than c2*n So all you know now is that from a certain point onward ( x big enough) your algorithm will run faster than c2*n and slower than c1*n*log(n) .
f(x) = Theta(g(x)) means that for x big enough there is some c3 > 0 and c4 > 0 so that c3*g(x) <= f(x) <= c4*g(x) , this means f(x) will only run a constant factor faster or slower than g(x) . So indeed, f(x) = O(g(x)) and f(x) = Omega(g(x)) . Conclusion: With only O and Omega given, if they are not the same you cannot conclude what Theta is. If you have the algorithm you could try and see if O was maybe chosen too high, or Omega might have been chosen too low.
链接地址: http://www.djcxy.com/p/6834.html上一篇: 这个游戏背后的数学/计算原理是什么？
下一篇: 解决Big Theta标记