Textbook
For sufficiently large natural $n$, the functions satisfy $f(n)\ge0$ and $g(n)>0$. The statement $f\in\Theta(g)$ means constants $c,C>0$ and $n_0$ satisfy $c g(n)\le f(n)\le C g(n)$ for all $n\ge n_0$. It combines an upper and a lower bound.
For $f(n)=3n+7$ and $n\ge1$, $3n\le3n+7\le10n$. Hence $f\in\Theta(n)$. This class allows different constant factors and lower-order terms; membership does not say the function equals $n$ or that its ratio to $n$ tends to 1.
For fixed base $b>1$, $\log_b n=\ln n/\ln b$. Thus $\Theta(\log_b n)=\Theta(\ln n)$: the base changes a constant multiplier, not the order. Numerical logarithm values still differ.
For an algorithm, the input size, unit-operation model, case, and resource must be specified. A procedure that always scans $n$ elements with fixed work per element and fixed setup work has time $\Theta(n)$ in that model. This says nothing automatically about its memory use.
The two initial bounds may start at different thresholds. If the upper bound works from $n_1$ and the lower bound from $n_2$, their common threshold can be $\max(n_1,n_2)$; both apply afterwards. Establishing membership in $\Theta(g)$ requires both inequalities. An upper bound alone leaves room for functions growing substantially more slowly beneath the same ceiling, so it cannot provide a tight order.
Definitions and notation: Mathematics for Computer Science.
Related concepts: Big O: an upper growth bound, Big Omega: a lower growth bound.
In plain language
A tight order bound traps a function in a corridor between two constant multiples of one scale. The floor and ceiling contain the entire sufficiently distant tail even if the function fluctuates between them. Costs of 3n and 7n have the same order, but the processor still pays the difference on a particular input. Theta describes the corridor’s scale rather than an exact route; the asymptotic sign on the door need not match a stopwatch reading.
Example
For the constructed function $3n+7$, the fixed bounds are $3n$ and $10n$. The example covers three input sizes.
Big Theta: a tight growth order
Small input
At n = 1, cost touches the upper bound.
Step 1 of 4: Small input
Read all steps
Small input
At n = 1, cost touches the upper bound.
- Lower; cost; upper
- 310included10
Larger input
At n = 10, the function stays within the same linear bounds.
- Lower; cost; upper
- 3037included100
Larger still
At n = 100, the bounds still use constants 3 and 10.
- Lower; cost; upper
- 300307included1000
Both bounds
One double inequality works for the entire tail n ≥ 1.
- c; C; n₀
- 3included10included1included
At $n=100$, the lower bound is 300, the function is 307, and the upper bound is 1000. The large gap above is harmless: a bound must hold, not hug every value tightly. All steps use the same coefficients 3 and 10. The final double inequality connects the examples with one general argument and establishes both sides simultaneously for every $n\ge1$.
Theta needs both bounds. An upper bound alone, however plausible, does not establish a tight order.