Why asymptotic comparison is appropriate for algorithms that solve a problem

Problem. Suppose two algorithms A and B satisfy ${T_B(n) \leq 3\,T_A(n)}$. In big‑O notation, ${B \in \mathcal O(T_A)}$, and in fact the two count as equally good: the notation does not rank B as worse even though it may be three times slower. Why is it reasonable for asymptotic notation to discard a factor of 3?

Cost assignments #

Fix an algorithm with input space $X$ which uses ${k \in \mathbb N}$ operation types, with costs ${c = (c_1, \ldots, c_k) \in \mathbb R_{>0}^k}$. The total cost function is then defined as

$$\begin{aligned} &T_c : X \to \mathbb R_{\geq 0}, \\ &T_c(x) = \sum_i c_i\, N(i, x), \end{aligned}$$

where ${N : \{1, \ldots, k\} \times X \to \mathbb N}$ gives how many times the $i$-th operation is executed on the input $x.$

Proposition. Given two cost assignments ${c, c'}$, there exist ${\alpha, \beta > 0}$ such that

$$\alpha\, T_{c'}(x) \leq T_c(x) \leq \beta\, T_{c'}(x);$$

in particular, it holds for ${\alpha = \min \Delta}$, ${\beta = \max \Delta}$, where(1) (1)Observe that a constraint here is that the operations to which a nonzero cost is assigned don’t change.

$$\Delta = \left\{ \frac{c_i}{c_i'} \right\}.$$

Cost by input size #

Now assume there is a size function ${s : X \to \mathbb N}$ and a least upper bound of cost by size, ${\mathcal T_c : \mathbb N \to \mathbb R_{\geq 0}}$, so that ${T_c(x) \leq \mathcal T_c(s(x))}$. In particular,

$$\mathcal T_c(n) = \sup_{s(x) = n} T_c(x).$$

Consider two algorithms A and B, with bound functions ${\mathcal T^A_c, \mathcal T^B_c}$, such that ${\mathcal T^B_c \in \mathcal O(\mathcal T^A_c)}$. This inclusion is invariant under changes of cost assignment, because for any cost change

$$\alpha\, \mathcal T_{c'} \leq \mathcal T_c \leq \beta\, \mathcal T_{c'}.$$

Asymptotic comparison #

A function $g$ is big‑O of $f$ iff $g$ is eventually no greater than a scaled version of $f.$ Since changing ${(c_1, \ldots, c_k)}$ alters an algorithm’s cost only up to a factor in ${[\alpha, \beta]}$, and asymptotic comparison is insensitive to such bounded factors, it is appropriate to use it to classify an algorithm’s cost behaviour independently of the arbitrary choice of costs, for a fixed machine model.

This reasoning extends to $\Theta$ and $\Omega.$