witness constants c and n0

Every Big-O, Big-Omega, or Big-Theta claim is, underneath the notation, a promise of the form 'after some point, one function stays within a constant multiple of another'. The two numbers that make that promise concrete are the witness constants: c, the constant multiple, and n0, the point after which the bound holds. To prove an asymptotic claim is literally to exhibit these two witnesses.

Think of them as answers to two questions. The constant c answers 'within what factor?' — it absorbs the difference between, say, 3n and n, so you do not have to track exact coefficients. The threshold n0 answers 'starting from what size?' — it lets you ignore the messy behavior at small n, where lower-order terms can dominate. For Big-O you need a single pair (c, n0) with f(n) <= c times g(n) for all n >= n0. Crucially, you do NOT need the smallest possible c or n0; any pair that works proves the bound. If c = 5, n0 = 1 works, then c = 1000, n0 = 1 works too — being generous with c often makes the algebra trivially easy.

This is why an asymptotic proof feels like a small game: rewrite f(n), bound each term by a multiple of g(n) for large enough n, add up the multiples to get c, and record the n where your bounds kicked in as n0. The witnesses are not unique and you are free to pick convenient ones. The same pattern works for Omega (flip to >=) and for Theta (two constants, c1 and c2, one on each side).