Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Big O, Theta, Omega

  1. Sep 18, 2012 #1
    I am getting a little confused over the notations of Big O, Theta, and Omega. I am completely fine with the formal definitions. This is what is confusing me.

    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!
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted