Concepts / Asymptotic Analysis of Algorithms

Asymptotic Analysis of Algorithms

Θ(n²) and Θ(n³) describe growth trends, and asymptotic analysis compares algorithms by those trends for large problem sizes.

  • Programming

Two Labels and a Tempting Verdict

Once you can describe an algorithm's run time with Big Theta notation, the natural next question is which of two algorithms is better. Suppose two algorithms solve the same problem. One has run time Θ(n²) and the other has run time Θ(n³). It is tempting to treat the smaller exponent as a verdict and conclude that the first algorithm wins. That conclusion is partly right and partly misleading. The difference between the two halves is the core idea of this article.

What do you think happens?

With only the labels Θ(n²) and Θ(n³), which algorithm finishes faster on one particular input of size 100?

  • The Θ(n²) algorithm, because its exponent is smaller

  • The Θ(n³) algorithm, because its cost is always smaller at size 100

  • The labels cannot decide this, because they do not capture constant factors or small-input behavior

Reveal answer
Answer:

The labels cannot decide this. They are claims about the eventual shape of each curve, not exact timings at one size.

The source states that the two labels can be compared only in the limit of large inputs, and that a single point on the curve can fall in either order. The labels do not capture the constant multipliers or small-input details, so they cannot settle which algorithm is faster at n = 100 on their own.

What the Big Theta Labels Actually Describe

Big Theta notation describes an algorithm's run time in terms of its asymptotic upper and lower bounds. Θ(n²) says that the growth of the run time is pinned to the shape of n squared. Θ(n³) says it is pinned to the shape of n cubed. Those shapes are what asymptotic analysis compares. The notation deliberately ignores the exact constant multipliers and the small-input details. That is why it is a statement about trends rather than exact timings.

Definition

Asymptotic analysis compares algorithms by their growth trends for large problem sizes. A Θ label is a claim about the eventual shape of an algorithm's run time, not a prediction of its exact time at any single input size.

Tracing Two Algorithms at Small Sizes

The source uses hypothetical constants to make the crossover visible. These numbers are invented for illustration and are not taken from any specific algorithm. Suppose the Θ(n³) algorithm performs about 1 · n³ basic steps, and the Θ(n²) algorithm performs about 100 · n² basic steps. We can trace both costs as the input size n grows. Each row below is a direct calculation from those two formulas.

Worked example

Tracing the two hypothetical cost formulas

The Θ(n³) algorithm does 1 · n³ basic steps and the Θ(n²) algorithm does 100 · n² basic steps. For each input size n, which algorithm does fewer basic steps?

  1. 1
    Write both cost formulas

    Cubic cost is 1 · n³, which equals n³. Quadratic cost is 100 · n², which equals 100n².

  2. 2
    Trace n = 10

    Cubic: 10³ = 1,000 steps. Quadratic: 100 × 10² = 10,000 steps. The cubic algorithm is cheaper here.

  3. 3
    Trace n = 100

    Cubic: 100³ = 1,000,000 steps. Quadratic: 100 × 100² = 1,000,000 steps. The two costs are exactly equal at this size.

  4. 4
    Trace n = 1,000

    Cubic: 1,000³ = 1,000,000,000 steps. Quadratic: 100 × 1,000² = 100,000,000 steps. Now the quadratic algorithm is ten times cheaper.

  5. 5
    Trace n = 10,000

    Cubic: 10,000³ = 10¹² steps. Quadratic: 100 × 10,000² = 10¹⁰ steps. The quadratic algorithm is now one hundred times cheaper.

Result

The cubic algorithm wins for small n, the two tie at n = 100, and the quadratic algorithm wins for every larger size shown, by a margin that keeps growing.

n = 10cubic 1,000 vs quadratic10,000n = 100cubic 1,000,000 vsquadratic 1,000,000n = 1,000cubic 1,000,000,000 vsquadratic 100,000,000n = 10,000cubic 10¹² vs quadratic10¹⁰costs meetquadratic pulls aheadgap grows
At what input size does the n² algorithm's running time drop below the n³ algorithm's, and how do the two costs cross as n grows? Under the hypothetical constants 1 · n³ and 100 · n², the costs are equal at n = 100 and the quadratic cost is lower beyond that.

Read the diagram from left to right as n grows. At n = 10, the cubic cost is smaller. At n = 100 the two costs meet, which is the crossover. After that, the quadratic cost stays lower and the distance between them keeps widening. The diagram shows these hypothetical numbers only. The real crossover for any two algorithms depends on their actual constants.

Why the Exponent Eventually Wins

Because one curve grows like n² and the other like n³, the cubic curve rises more steeply. The source describes the consequence: as the problem size keeps increasing, the relative advantage of the Θ(n²) algorithm keeps growing. The ratio between the two eventually reaches factors of a thousand, a million, a billion, and beyond.

The reason the ordering eventually flips lies in how a multiplicative constant interacts with a higher power of n. For any positive constants a and b, the function a·n³ grows faster than b·n² as n gets larger. This holds no matter how small a is or how large b is. Constants shift the curves, but they cannot change which power dominates in the long run.

Rule

The formula above shows the ratio of the cubic cost to the quadratic cost. For fixed positive constants a and b, the ratio is a fixed factor multiplied by n. A ratio that keeps growing means the cubic function eventually exceeds any fixed multiple of the quadratic one. A large constant b can delay this for a while, but it cannot stop it.

Watching the Gap Widen

The advantage of the slower-growing algorithm does not stay fixed. Using the hypothetical constants from earlier, the cubic cost divided by the quadratic cost equals n divided by 100. When n doubles, that ratio doubles. When n grows by a factor of 10, the ratio grows by a factor of 10 as well. The timeline below walks through this widening gap at four input sizes.

n = 100ratio 1×n = 1,000ratio 10×n = 10,000ratio 100×n = 100,000ratio 1,000×n grows ×10n grows ×10n grows ×10
As n grows, how much does the cubic algorithm fall behind? Under the hypothetical constants, the cubic cost divided by the quadratic cost equals n / 100, so the lead of the quadratic algorithm multiplies with every increase in n.

Each step on the timeline is a tenfold increase in n, and each step multiplies the cubic algorithm's disadvantage by ten. The source's phrase about ratios reaching a thousand, a million, a billion, and beyond describes exactly this behavior, continued over larger sizes.

Why Labels Cannot Pick a Winner at One Size

The labels alone cannot tell you which algorithm wins at one specific size. Constant factors and small-input behavior are not captured by Θ notation. The source is explicit that the analysis alone does not reveal how large large has to be. The comparison below holds the input at n = 50 and shows the two hypothetical costs side by side, to show how a label can mislead at a single size.

Θ(n³) algorithm1 · n³ = 125,000 stepsΘ(n²) algorithm100 · n² = 250,000 steps
Do the asymptotic labels determine which algorithm is faster at n = 50? With the hypothetical constants 1 · n³ and 100 · n², the cubic algorithm is cheaper at this size even though its label is the larger one.

At n = 50, the cubic algorithm performs 125,000 steps and the quadratic algorithm performs 250,000. The larger label belongs to the faster algorithm at this size. The labels did not predict this. The constant 100 in front of the quadratic term made the quadratic algorithm more expensive at small n, even though the quadratic term wins in the long run.

  • Common mistake

    Treating the smaller exponent as proof that the algorithm is faster at every input size

    What it looks like

    Concluding that the Θ(n²) algorithm is faster at n = 10 because 2 is less than 3.

    Why it fails

    The labels describe the eventual shape of the curve. At n = 10 with the hypothetical constants, the Θ(n³) algorithm does 1,000 steps and the Θ(n²) algorithm does 10,000.

    Do this instead

    Use the labels to predict behavior for large inputs, and check actual constants or measurements for a specific size.

  • Common mistake

    Assuming the crossover is always at the same place for any pair of Θ(n²) and Θ(n³) algorithms

    What it looks like

    Expecting every quadratic algorithm to beat every cubic one at n = 100.

    Why it fails

    The crossover depends on the constant factors, which the labels ignore. Different constants move the crossover point.

    Do this instead

    Treat the crossover as a property of the specific algorithms, not of the labels alone.

  • Common mistake

    Reading the source's preference as a guarantee for small inputs

    What it looks like

    Choosing a Θ(n²) algorithm for a tiny input without checking anything else.

    Why it fails

    The source says a Θ(n²) algorithm is generally preferred when no other information is available, and that it is often faster even for fairly small inputs. It does not say it is always faster at every small size.

    Do this instead

    Prefer the Θ(n²) algorithm as the default when no other information exists, but verify when the input size or constants are known.

Practice: Reading the Crossover

MEDIUM

Using the hypothetical costs 1 · n³ for one algorithm and 100 · n² for the other, find the input size at which the two costs are equal. Then state which algorithm is cheaper for n = 20 and for n = 500.

Hints
  • Set n³ equal to 100n² and solve for n, assuming n is positive.
  • For n = 20, compare 20³ with 100 × 20². For n = 500, compare 500³ with 100 × 500².
  • Remember that the source's ratio, the cubic cost divided by the quadratic cost, equals n divided by 100.
HARD

Suppose a Θ(n³) algorithm does 1 · n³ steps and a Θ(n²) algorithm does 1,000 · n² steps. Without computing every case, explain whether the crossover point moves to a larger or smaller n than in the 100 · n² example, and why the labels alone cannot give you the exact new crossover.

Hints
  • Think about which algorithm's constant is larger, and what that does at small n.
  • The labels stay the same in both examples, so ask what changed between them.

Key Takeaways

  • Θ(n²) and Θ(n³) are growth-trend labels, and asymptotic analysis compares algorithms by those trends for large problem sizes.
  • For large enough inputs, the Θ(n²) algorithm is guaranteed to be faster, and its advantage keeps growing as the input grows.
  • Because constants cannot change which power of n dominates in the long run, the ordering eventually flips in favor of the slower-growing algorithm, regardless of the constants.
  • The labels alone cannot say which algorithm wins at one specific size, because constant factors and small-input behavior are not captured by the notation.
  • When no other information is available, a Θ(n²) algorithm is generally preferred over a Θ(n³) one, and it is often faster even for fairly small inputs.

Related Topics