What exactly does big Ө notation represent?
algorithm, big-o, computer-science, notation
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`
Problem
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?