Big O Theta Omega question

Discussion in 'OT Technology' started by RiKuN, Oct 12, 2006.

  1. RiKuN

    RiKuN New Member

    Joined:
    Sep 20, 2006
    Messages:
    37
    Likes Received:
    0
    One of my hw questions asks: show that the worst-case running time of quick-select on an n-element sequence is Big Omega(n^2).

    Isn't Big Omega supposed to be the best case scenario? Is the question asking what's the worst best case scenario?
     
  2. Coottie

    Coottie BOOMER......SOONER OT Supporter

    Joined:
    Jun 6, 2006
    Messages:
    32,407
    Likes Received:
    0
    Location:
    OKC
    Big Omega can be considered the lower boundary of your function. In other words: past a certain point, your function will always be greater than the function it's big omega to.

    Or said even another way. f(x) = BigOmega(g(x)) if for every x past a certain value f(x) >= g(x).

    Hope that helps.
     
  3. Bruticus

    Bruticus half dead OT Supporter

    Joined:
    Apr 10, 2004
    Messages:
    4,608
    Likes Received:
    0
    Location:
    Melbourne
    You can use it for all 3 ways (best case, average, worst). You just have to specify which one you are doing it for.
     

Share This Page