Theta, O and Omega…

The first recitation lecture of Introduction to algorithms gives a different introduction to the asymptotic complexity.

  • Theta (n) is when you can get a function g(x) and constants m and n such that our candidate complexity function f(x) is between m.g(x) and n.g(x) – i.e Theta(n) can be said if we can find a function such that it can serve as both tight upper and lower bounds of the candidate function
  • When such a function is not possible (lets say we have a sin(x) in the function, per lecture), then we can only find a function g(x) such that f(x) is not more than m.g(x) (there is no “not less than” clause) here. When this is the case, we have O(n)
  • When there are both lower bounds and upper bounds for the candidate function f(x), but the lower and upper bounds are not with in a constant factor away, then Theta cannot be used. We can use Omega(lb(x)) or O(ub(x)) – where lb(x) and ub(x) are the lower and the upper bound functions in x respectively.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s