Hacker Timesnew | past | comments | ask | show | jobs | submitlogin

I remember from college there was big-Oh `O(x)` and little-Oh `o(x)`. Is Omega/Theta the same as little-Oh?


No, big O is a kind of loose upper bound, while little-O is a very strict upper bound.

  f(x) = O(g(x)) <=> there exists k, x0 such that f(x) < k * g(x) for any x > x0

  f(x) = o(g(x)) <=> for any k > 0, there exists x0 s.t. f(x) < k * g(x) for any x > x0
For example:

  f(n) = 3*n^2 + 2n + 1

  f(n) = O(n^2)? 
     let's take k = 10
     3*n^2 + 2n + 1 < 2 * n^2 for any n > n0?
     n = 0: 3 * 0^2 + 2*0 + 1 < 10 * 0^2 <=> 1 < 0 false
     n = 1: 3 * 1^2 + 2*1 + 1 < 10 * 1^2 <=> 6 < 10 true
     n = 2: 3 * 2^2 + 2*2 + 1 < 10 * 2^2 <=> 17 < 40 true
     ...
     so, yes, f(n) = O(n^2) (n0 = 1)

  f(n) = o(n^2) ? 
    let's take k = 2.
    
     3*n^2 + 2n + 1 < 2 * n^2 for any n > n0?

     3 * n^2 + 2 * n + 1 < 2 * n^2      <=>
     3 * n^2 + 2 * n + 1 - 2 * n^2 < 0  <=>
     n^2 + 2 * n + 1 < 0 false for any n > 0.

     so no, f(n) != o(n^2). However, f(n) = o(10 * n^2), and f(n) = o(n^3).

Big-Omega and small-Omega are the same idea for a lower bound.

Big-Theta is a tight bound around the function:

  f(n) = Theta(g(n)) <=> there exists k1, k2, n0 such that k1*g(n) < f(n) < k2*g(n), for any n > n0.
There is no equivalent "little-theta", as that would imply that the relation must hold for any k1 and k2, which would at best leave only the function itself as fulfilling the condition.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: