Recipe

Find where one function eventually dominates another

Use when: you're given two functions f and g and asked whether one stays ahead of the other forever, past some point

Goal: the crossover point N beyond which f(n) >= g(n) for every n >= N, or a reason no search is needed

Taught in Growth of functions: a first look

1. 1

   Plug in n=1,2,3,... in order and record f(n) and g(n) side by side, watching for the lead to switch.

   Example

   For f(n)=n^2, g(n)=2^n: at n=3, 9 vs 8 (f ahead); at n=4, 16 vs 16 (tied); at n=5, 25 vs 32 (g ahead).

   • the two functions belong to known families with a settled ordering (\log n, a power of n, an exponential c^n, or n!) — skip the numeric search and cite that ordering directly.
   • neither function fits a known family, or the comparison is close — keep computing values by hand until the lead stops flipping.

   Why: eventual domination is a long-run property, so the only way to find where the lead settles is to track it as n actually grows.

2. 2

   Once one function pulls ahead, compute a few more values past that point to make sure it does not fall back behind again.

   Example

   Past n=5, 2^n roughly doubles each step while n^2 only grows by about 2n+1, so 2^n stays ahead at n=6,7,8.

   ⚡ Shortcut

   When f(n)-g(n) has an easy-to-determine sign for every n, that alone proves domination with no crossover search at all. For f(n)=n^2+100n, g(n)=n^2: f(n)-g(n)=100n>0 for every n\ge1, so f dominates from n=1 onward.

   Why: a lead that holds for a few values is not automatically permanent, and domination requires the lead to hold for every n from that point on, forever.

3. 3

   Report the smallest N where the final lead begins, and name which function eventually dominates.

   Example

   N=5: 2^n eventually dominates n^2, even though n^2 led at n=1,2,3 and tied at n=4.

   Why: reporting the exact crossover point, not just "eventually," is what makes the claim checkable by re-running the same computation.