- #1

doubleaxel195

- 49

- 0

A problem P has worst case time complexity O(f(n)) and Omega(g(n)). Does this mean that P has worst case time complexity Theta(h(n)) for g(n) <=h(n) <=f(n)? If this were true, there could be an algorithm that solves P better than O(f(n)) (namely O(h(n))? Or is there no possible h(n) where P is Theta(h(n)), which would mean there is no algorithm that can solve P better than O(f(n))?

Thanks in advanced!