Five Common Rules for Analyzing the Runtime

Review the five common rules of runtime analysis of the algorithms.

We'll cover the following

Rule #1

This rule states that multiplicative constants can be omitted:

cffc\cdot f\preceq f.

Examples: 5n2n25n^2\preceq n^2, n23n2\frac{n^2}{3}\preceq n^2, 7nn7n\preceq n.

Rule #2

This rule states that out of two polynomials, the one with a larger degree grows faster:

nanbn^a\prec n^b for 0a<b0\leq a<b

Examples: nn2n\prec n^2, nn23\sqrt{n} \prec n^\frac{2}{3}, n2n3n^2 \prec n^3, n0nn^0\prec \sqrt{n}.

Rule #3

This rule states that any polynomial grows slower than any exponential:

nabnn^a \prec b^n for a0a \geq 0, b>1b>1

Examples: n32nn^3 \prec 2^n, n101.1nn^10 \prec 1.1^n.

Rule #4

This rule states that any polylogarithm—that is, a function of the form (logn)a(\log n)^a—grows slower than any polynomial:

(logn)anb(\log n)^a \prec n^b for a,b>0a, b > 0

Examples: (logn)3n(\log n)^3 \prec \sqrt{n}, nlognn2n\log n \prec n^2

Rule #5

This rule states that smaller terms can be omitted:

fgf \preceq g, then f+ggf+g \preceq g.

Examples: n+n2n2n+n^2 \preceq n^2, n9+2n2nn^9+2^n \preceq 2^n.