Computational cost #

In this section, we briefly introduce the standard way to estimate the cost of an algorithm, as a function $f(n)$ of the size $n$ of its input.

Size #

The size $n$ of the input may be the size of its representation in bits.

Other common measures include:

• the number of entries for array,
• the number of nodes for tree,
• etc.

Time or memory #

Among others, the function $f(n)$ may estimate:

• the running time of the algorithm, or
• its memory consumption.

Worst case, average #

Among others, the function $f(n)$ may estimate:

• cost in the worst case, i.e. for the worst possible inputs of size $n$, or
• average cost over all possible inputs of size $n$.

boolean contains(int[] A, int a){
    foreach(v in A) {
        if(v == a){
            return true
        }
    }
    return false
}

boolean contains(int[] A, int a){
    int begin = 0
    int end = A.lenghth - 1
    while(begin < end){
        mid = (begin + end) / 2
        if(a <= A[mid]){
            end = mid
        } else {
            begin = mid + 1
        }
    }
    return A[begin] == a
}

Asymptotic cost #

When comparing the costs of algorithms, we are usually interested in scalability, i.e. how they behave when the input gets large.

Let $f(n)$ measure the (worst case or average) running time of an algorithm.

If $n$ doubles, does $f(n)$ double as well? In other words, does $f(2 n) = 2 f(n)$?

If this is the case, then $f$ is a linear function.

Examples. The following are linear functions:

• $f(n) = n$
• $g(n) = 5n$
• $h(n) = \frac{1}{2} n$

Alternatively, if $f(2 n) > 2 f(n)$, then the cost grows more than linearly with the size of the input.

Examples.

• if $f(n) = n^2$, then $f(2n) = 4 f(n)$,
• if $f(n) = c n^2$ for some $c$, then $f(2n) = 4 f(n)$ as well,
• if $f(n) = n^3$, then $f(2n) = 8 f(n)$,
• if $f(n) = 2^n$, then $f(n+1) = 2 f(n)$

Alternatively, $f(n)$ may grow less than linearly with $n$.

Examples.

• if $f(n) = \sqrt{n}$, then $f(4n) = 2f(n)$
• if $f(n) = \sqrt[3]{n}$, then $f(8n) = 2f(n)$
• if $f(n) = \log_2 n$, then $f(2n) = f(n) + 1$

Comparing cost functions #

Two cost functions $f$ and $g$ are said to be asymptotically equivalent if they intuitively have the same growth.

Examples.

• all linear functions are asymptotically equivalent,
• the functions $f(n) = n^2$ and $g(n) = 3n^2$ are asymptotically equivalent.

Terminology. A function $f: X \to Y$ is monotone if $x_1 \le x_2$ implies $f(x_1) \le f(x_2)$ for any $x_1, x_2 \in X$.

Definition. Let $f$ and $g$ be two monotone functions over $\mathbb{N}$ such that $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ is defined. And let $l$ be this limit.

• if $l = 0$ then $g$ outgrows $f$,
• if $l = \infty$ then $f$ outgrows $g$,
• otherwise (i.e. if $l \in \mathbb{R}$ and $l \neq 0$), $f$ and $g$ are asymptotically equivalent.

In practice #

Hint. $f$ outgrows $g$ iff the derivative of $f$ outgrows the derivative of $g$.

Example. Let $f(n) = 5n^2$ and let $g(n) = n^3$.

Then $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{5n^2}{n^3} = \lim_{n \to \infty} \frac{10n}{3n^2} = \lim_{n \to \infty} \frac{10}{6n} = 0$

So $g$ outgrows $f$.

Example. Let $f(n) = 5n^2$ and let $g(n) = n^2$.

Then $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{5n^2}{n^2} = \lim_{n \to \infty} \frac{10n}{2n} = 5$

So $f$ and $g$ are asymptotically equivalent.

Hint. If there exists a function $h$ over $\mathbb{N}$ such that

• $\lim_{n \to \infty} h(n) = \infty$ and
• $f(n) = g(n)h(n)$,

then $f$ outgrows $g$.

Example. Let $f(n) = n \cdot \log_2 n$ and let $g(n) = n$.

Take $h(n) = \log_2 n $.

Then

• $\lim_{n \to \infty} h(n) = \lim_{n \to \infty} \log_2(n) = \infty$, and
• $f(n) = n \cdot \log_2 n = g(n) h(n)$,

Therefore $f$ outgrows $g$.

Equivalence classes #

Notation. If $f$ is a cost function, then $\Theta(f)$ is used to denote the set of all cost functions that are asymptotically equivalent to $f$ (including $f$ itself).

Example. If $f(n) = n$, then the class $\Theta(f)$ contains the functions:

• $g(n) = 2n$,
• $h(n) = \frac{n}{2}$,
• $j(n) = 3n + 4$,
• etc.

Notation. If $\Theta(f)$ is a class of cost functions, then the name of the function ("$f$" here) can be omitted. Instead, the definition of $f$ is used (typically with $n$ as variable).

Examples.

• if $f(n) = n$, then the class $\Theta(f)$ is usually denoted with $\Theta(n)$,
• if $f(n) = n^2$, then the class $\Theta(f)$ is usually denoted with $\Theta(n^2)$,
• etc.

Note. If $g$ is in $\Theta(f)$, then $\Theta(f)$ and $\Theta(g)$ are the same class.

A simple, representative function is usually preferred to denote in each class.

Example. $\Theta(n)$, $\Theta(\frac{n}{2})$ and $\Theta(3n+4)$ are three alternative notations for the same class of cost functions.

For readability, $\Theta(n)$ is usually preferred.

Some of the most frequent classes of cost functions for algorithms are (from lower to higher cost):

• $\Theta(1)$ (a.k.a. constant cost)
• $\Theta(\log n)$ (a.k.a. logarithmic cost)
• $\Theta(n)$ (a.k.a. linear cost)
• $\Theta(n \log n)$
• $\Theta(n^2)$ (a.k.a. quadratic cost)
• $\Theta(n^3)$ (a.k.a. cubic cost)
• $\Theta(2^n)$

Useful simplifications #

The definition of asymptotic equivalence implies that the cost function of an algorithm can often be simplified into an equivalent one, using simple rules. We list here a few of them.

Simplification rule. If $f(n) = c \cdot g(n)$ for some constant $c$, then $f$ is in $\Theta(g)$.

Examples.

• $f(n) = 3n$ is in $\Theta(n)$
• $f(n) = 2n^3$ is in $\Theta(n^3)$
• $f(n) = 5 \log n$ is in $\Theta(\log n)$
• etc.

Simplification rule.

• if $f(n) = \log_a n$ (for some base $a$), then $f$ is in $\Theta(\log n)$
• if $f(n) = n \log_a n$ (for some base $a$), then $f$ is in $\Theta(n \log n)$
• etc.

Examples.

• $f(n) = \log_2 n$ is in $\Theta(\log n)$
• $f(n) = \frac{1}{5} \log_3 n$ is in $\Theta(\log_3 n) = \Theta(\log n)$
• $f(n) = 4n \log_2 n$ is in $\Theta(n \log_2 n) = \Theta(n \log n)$

Simplification rule. If $f(n)$ is a sum of terms (e.g. a polynomial), then it belongs to the class that represents the highest order term.

Examples.

• $f(n) = 2n^2 + 3n + 20$ is in $\Theta(2n^2) = \Theta(n^2)$
• $f(n) = \frac{3}{2}n^3 + 2n^2 + 3n + 20$ is in $\Theta(\frac{3}{2}n^3) = \Theta(n^3)$
• $f(n) = 2 n\log(n) + 3n + \sqrt{n}$ is in $\Theta(2 n \log n) = \Theta(n \log n)$

Big $O$ #

Notation. $O(f)$ denotes the union of all classes of functions that are at most as expensive as $f$ (asymptotically).

Example. $f(n) = 3n + 5$ is in $\Theta(n)$, therefore the following also hold:

• $f$ is in $O(n^2)$
• $f$ is in $O(n^2 \log n)$
• $f$ is in $O(n^{2.5})$
• $f$ is in $O(n^3)$
• $f$ is in $O(2^n)$

Note. As a consequence,

$\qquad f$ is in $\Theta(g)$

is syntactic sugar for

$\qquad f$ is in $O(g)$ and $g$ is in $O(f)$

Overloaded equality #

Warning. Instead of “$f$ is in $\Theta(g)$”, it is customary to write:

$\qquad f(n) = \Theta(g)$

(and similarly for $O$), thus overloading the meaning of the symbol “$=$”.

Examples.

• $f(n) = 3n^2 + 5 = \Theta(n^2)$
• $f(n) = 2 n^2 \log n = \Theta(n^2 \log n)$
• $f(n) = 2 n^2 = O(n^2)$
• $f(n) = 2 n^3 = O(n^3)$

Application #

Let us now evaluate the asymptotic cost of some algorithms.

For simplicity, we will focus of the worst-case running time (but the same notion of asymptotic cost can be used for average cost and/or memory usage).

RAM cost model #

The so-called Random Access Machine (RAM) model of computation makes several assumptions about computational cost. In particular, for a given index $i$, the cost of accessing the $i^\text{th}$ element of an array does not depend on the size of this array.

Another simplification that is often made (although not consistently by all authors) in the RAM model is that the cost of a value comparison or a basic arithmetic operation (e.g. addition or multiplication) does not depend on the values of its operands.

Example. Consider the following method

boolean myMethod(int[] A, int i){
    return A[i] + A.length
}

Let $n$ be the size of the input array $A$, and let us express the running time of this method as a function of $n$. If we adopt the RAM cost model, then:

• the cost $c_1$ of reading the value A[i] is independent of $n$
• the cost $c_2$ of reading the length of A is also independent of $n$
• the cost $c_3$ of summing these two values is also independent of $n$

Therefore, expressed as a function $f$ of $n$, the running time of this method is

$\qquad f(n) = c_1 + c_2 + c_3$

which is in $\Theta(1)$.

In other words, the running time of this method is constant in the size of the array.

Example. Consider the same algorithm as above (but where the meaning of foreach is made explicit)

1 2 3 4 5 6 7 8 9 10

boolean contains(int[] A, int a){ int i = 0 while (i < A.length) { if(A[i] == a){ return true } i++ } return false }

Once again, let $n$ be the size of the input array A, and let us express the worst case running time of this method as a function of $n$.

Recall that the worst possible input is the one where the input value a does not appear in A. In this case, the loop is executed $n$ times.

If we adopt the RAM cost model:

• the cost $c_1$ of the initialization of i (line 2) is independent of $n$
• the cost $c_2$ of one comparison of i with A.length (line 3) is independent of $n$
• the cost $c_3$ of one execution of the loop is independent of $n$
• the cost $c_4$ of the final return statement (line 8) is independent of $n$

Therefore, expressed as a function $f$ of $n$, the cost of this method is

$$ f(n) = c_1 + c_2 n + c_3 n + c_4 $$

$$ \qquad\ \ = (c_2 + c_3) n + c_1 + c_4 $$

which is in $\Theta(n)$.

In other words, the worst-case running time of this method is linear in the size of the array.