Big-Theta as a tight bound
/ big THAY-tuh /
Big-Theta is the notation you use when you know the growth exactly, not just a one-sided bound. Saying a cost is Theta(n log n) means it grows like n log n from both directions: it is squeezed between two constant multiples of n log n for large inputs. If Big-O is a ceiling and Big-Omega is a floor, Big-Theta is when the ceiling and floor are the same shape, pinning the function in place.
Formally, f(n) is Theta(g(n)) if there exist positive constants c1 and c2 and a threshold n0 such that c1 times g(n) <= f(n) <= c2 times g(n) for every n >= n0. Equivalently, and this is the handy version, f is Theta(g) exactly when f is both O(g) and Omega(g). So to prove a Theta bound you prove the ceiling and the floor separately. For 3n^2 + 5n + 2 we already saw it is <= 10n^2 (the O side); and clearly 3n^2 + 5n + 2 >= 3n^2 (the Omega side, with c1 = 3), so it is Theta(n^2): take c1 = 3, c2 = 10, n0 = 1.
Theta is the precise, honest claim most people actually mean when they sloppily say 'O'. 'Merge sort is Theta(n log n)' tells you the running time really does scale like n log n — not faster, not slower — which is far more informative than a bare upper bound. When a problem's best algorithm matches a proven lower bound, the two meet at a Theta and we say the problem is 'solved' asymptotically; sorting by comparisons, at Theta(n log n), is the classic example.
A double loop where the inner loop runs i times for outer index i from 1 to n does 1 + 2 + ... + n = n(n+1)/2 steps. That equals (1/2)n^2 + (1/2)n. It is Theta(n^2): bounded below by (1/2)n^2 and above by n^2 for n >= 1. We get the exact growth, both directions, not merely 'at most n^2'.
Prove O and Omega separately; when they match, you have a Theta.
f = Theta(g) requires BOTH an upper and a lower bound at the same growth rate. A function can be O(n^2) yet not Theta(n^2) if its true growth is smaller, e.g. an actually-linear cost.