algorithmcomputer-sciencenotationbig-o

What exactly does big Ө notation represent?

I'm really confused about the differences between big O, big Omega, and big Theta notation.

I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent?

I have read that it means tight bound, but what does that mean?

Solution

  • It means that the algorithm is both big-O and big-Omega in the given function.

    For example, if it is Ө(n), then there is some constant k, such that your function (run-time, whatever), is larger than n*k for sufficiently large n, and some other constant K such that your function is smaller than n*K for sufficiently large n.

    In other words, for sufficiently large n, it is sandwiched between two linear functions :

    For k < K and n sufficiently large, n*k < f(n) < n*K