Maths/Big O notation

Limits and dominance

After thiswhat you will be able to doCompare two growth rules by taking the limit of their ratio, and decide whether one eventually dominates the other or stays within a constant factor.

Questionwhat this lesson answersThe arc kept saying one shape eventually grows faster than another, a logarithm slower than any straight line, a square faster than any line. What does "eventually outgrows" mean exactly, and how do you establish it for certain instead of trusting a handful of values?

Not coveredwhat this lesson leaves outWe define dominance through the limit of a ratio and settle two cases the arc asserted. We do not develop the full theory of limits, and we do not prove the limits from their formal definition.

The arc has repeatedly used the phrase “eventually grows faster.” A repeated-halving count was said to grow more slowly than a straight line. A quantity made by multiplying the input by itself was said to outgrow one copy of the input. Those statements can be right even when the slower shape leads for a while. A few selected values cannot settle them, because a curve can look ahead at one range and lose later. The question is what “eventually outgrows” means exactly.

Take two rules that give a size for the same input. Call the rule being compared $g$, and call the other rule $f$. Divide the first size by the second at each input:

This quotient says how large $g$ is as a share of $f$ at that one input. It is called the ratio. Now let the input keep growing without any final largest value and watch where that ratio heads. If the values settle closer and closer to one single number, that destination is called the limit of the ratio. A ratio may fail to settle, so a limit is not automatic.

The comparison needed here is especially sharp. Suppose the ratio with the slower rule on top heads to zero:

Then eventually $g$ is a smaller share of $f$ than any fixed positive share you choose. Put differently, enough copies of the slower shape will still fit under one copy of the faster shape after some input. The relation is called dominance: $f$ dominates $g$ when the slower-over-faster ratio settles at zero. The word describes a long-run relation, not a claim that the faster shape must be larger at every small input.

The phrase “by any factor” has a concrete reading. If the ratio falls below one hundredth, one hundred copies of the slower rule fit below one copy of the faster rule at that input. If it falls below one millionth, a million copies fit. Settling at zero says this can be done for every chosen fixed number of copies, once the input is allowed to grow far enough.

First settle the debt from the logarithms lesson. A repeated-halving count is written with a logarithm. A straight-line count rises by one fixed amount for each added input item. To compare them, put the repeated-halving count over the line:

At a few well-separated inputs, its fall is visible:

The values head to zero. So the line dominates the base-two logarithm. No matter which fixed multiplier is attached to the logarithm, the line eventually outgrows it. That settles the claim behind writing the repeated-halving cost below a straight-line cost in Big O notation. The base does not rescue the logarithm, because changing the base only supplies another fixed multiplier.

Now compare a line with a square. A square is the input multiplied by itself. Put the line over that faster shape:

This ratio has no hidden behaviour. Each larger input makes one divided by the input smaller:

It heads to zero, so the square dominates the line. The calculation says more than a graph appearing steeper. It identifies the share of the square occupied by one line, and that share vanishes as the input grows.

Not every ratio heads to zero. Compare three copies of a line with one copy:

The ratio is always three. It settles, but at a fixed nonzero value. Neither rule dominates the other: each remains a constant multiple of the other. They belong to the same growth class. This is the throwing-away move from earlier in the arc stated honestly. A fixed multiplier changes a real count, but it does not make one shape eventually dwarf the other.

There is a deliberate limit to this lesson. We have read these limits from their values and their shape, not derived them from the formal definition of a limit. The falling values are strong evidence and the conclusions are correct in these cases. A full proof would show that after any requested closeness to zero, there is a threshold beyond which every later ratio stays that close. That machinery is its own subject.

The link to Big O is direct. A membership claim says one cost stays beneath a fixed multiple of another after a threshold. When the slower-over-faster ratio goes to zero, such a threshold must exist for any chosen fixed multiplier. The What O(f) actually is door gives that ceiling its formal witnesses.

The Doubling test uses a different quotient. It compares one cost at two input sizes, $n$ and $2n$, to read a possible shape. This lesson compares two shapes at one input size to decide who wins in the long run. Both use division, but they answer different questions.