Skip to content

Exercises · Running time

Exercises · Chapter 12 · each solution opens with a click · Chapter 12: Running time · Exercises, volume 4 (PDF)

In the exercises of this chapter the steps are counted with the conventions of the chapter «Running time»: every execution of a numbered line of pseudo-code (including the lines return) is one step, the condition of a while loop whose body is executed \(k\) times is evaluated \(k+1\) times, and the lines of a branch that is not taken are not executed. After the number of steps \(S(n)\), the running time is expressed as a function of the input size \(|I|\) with one of the following two rules.

Rule (A): the input is a natural number \(n\). Then \(|I|=\Theta(\log_2 n)\): there exist constants \(c_1,c_2>0\) such that, for all sufficiently large \(n\),

\[ c_1\log_2 n \le |I| \le c_2\log_2 n \qquad\Longleftrightarrow\qquad 2^{\frac{1}{c_2}|I|}\le n \le 2^{\frac{1}{c_1}|I|}, \]

since \(x\mapsto 2^x\) is strictly increasing and \(2^{\log_2 n}=n\). If \(S(n)=\Theta(n)\), there exist constants \(a_1,a_2>0\) such that \(a_1 n \le S(n) \le a_2 n\) for all sufficiently large \(n\), and therefore

\[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{that is,}\qquad T(|I|)=2^{\Theta(|I|)}. \]

Rule (B): the input is an array \(a[1..n]\) whose entries use a fixed constant number of bits. Then \(|I|=\Theta(n)\): there exist constants \(c_1,c_2>0\) such that, for all sufficiently large \(n\),

\[ c_1 n \le |I| \le c_2 n \qquad\Longleftrightarrow\qquad \frac{1}{c_2}|I| \le n \le \frac{1}{c_1}|I|. \]

If \(S(n)=\Theta(n^k)\) for a constant \(k\ge 1\), there exist constants \(a_1,a_2>0\) such that \(a_1 n^k \le S(n) \le a_2 n^k\) for all sufficiently large \(n\), and therefore

\[ \frac{a_1}{c_2^{k}}\,|I|^k \le S(n) \le \frac{a_2}{c_1^{k}}\,|I|^k, \qquad\text{that is,}\qquad T(|I|)=\Theta(|I|^k). \]

Exercise 12.1: Running time (E1)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 1

Input: A natural number \(n\)
Output: A natural number \(m\)
1function Algorithm1(n)
2\(m := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(m \leftarrow m+2\)
6\(i \leftarrow i+1\)
7end
8return \(m\)
9end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm adds \(2\) to \(m\) exactly \(n\) times, starting from \(m=0\): it determines the double of \(n\), that is \(2n\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm1, where \(n\) is the natural number given in input. There is only one input for each value of \(n\), so this is also the worst case. The body of the loop is executed for \(i=1,2,\dots,n\), that is \(n\) times, and the condition of line 4 is evaluated \(n+1\) times:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+4=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm1, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.2: Running time (E2)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 2

Input: A natural number \(n\)
Output: A natural number \(m\)
1function Algorithm2(n)
2if \(n \bmod 2 = 0\) then
3\(m := 0\)
4\(i := 1\)
5while \(i \leq n\) do
6\(m \leftarrow m+2\)
7\(i \leftarrow i+1\)
8end
9else
10\(m := n\)
11end
12return \(m\)
13end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm returns the double \(2n\) of \(n\) if \(n\) is even. If \(n\) is odd, it returns \(n\) unchanged.

  2. Let \(S(n)\) denote the number of steps executed by Algorithm2, where \(n\) is the natural number given in input. The execution of lines 3–7 depends on the specific input value \(n\): before executing the algorithm, we do not know whether \(n\) is even or odd. We define a function

    \[ t:\N\to\{0,1\}, \]

    where \(t(n)=1\) if \(n \bmod 2 = 0\), and \(t(n)=0\) otherwise. In other words, \(t(n)\) is an oracle that tells us whether the input number \(n\) is even. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(t(n)\)
    4 \(t(n)\)
    5 \(t(n)\,(n+1)\)
    6 \(t(n)\,n\)
    7 \(t(n)\,n\)
    10 \(1-t(n)\)
    12 \(1\)

    Therefore, the total number of steps is

    \[ 1+t(n)+t(n)+t(n)(n+1)+t(n)\,n+t(n)\,n+\big(1-t(n)\big)+1=3n\,t(n)+2\,t(n)+3. \]

    The worst possible case is when \(n\) is even: then \(t(n)=1\) and the algorithm executes \(3n+5\) steps, while for \(n\) odd it executes only \(3\) steps. Every input size of at least two bits is the size of some even numbers, so in the worst case

    \[ S(n)=3n+5=\Theta(n). \]

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+5=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm2, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.3: Running time (E3)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 3

Input: A natural number \(n\)
Output: A natural number \(s\)
1function Algorithm3(n)
2\(s := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(s \leftarrow s+i\)
6\(i \leftarrow i+1\)
7end
8return \(s\)
9end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the sum of the first \(n\) positive natural numbers:

    \[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]

  2. Let \(S(n)\) denote the number of steps executed by Algorithm3, where \(n\) is the natural number given in input (there is only one input for each value of \(n\)). The body of the loop is executed \(n\) times and its condition \(n+1\) times:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+4=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm3, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.4: Running time (E4)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 4

Input: A natural number \(n\)
Output: A natural number \(p\)
1function Algorithm4(n)
2\(p := 1\)
3\(i := 1\)
4while \(i \leq n\) do
5\(p \leftarrow p \cdot i\)
6\(i \leftarrow i+1\)
7end
8return \(p\)
9end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the product

    \[ 1\cdot 2\cdot \ldots \cdot n=n! \]

    (with \(0!=1\), returned for \(n=0\)).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm4, where \(n\) is the natural number given in input (there is only one input for each value of \(n\)). The body of the loop is executed \(n\) times and its condition \(n+1\) times:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+4=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm4, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.5: Running time (E5)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 5

Input: A natural number \(n\)
Output: A natural number \(c\)
1function Algorithm5(n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(i \bmod 2 = 0\) then
6\(c \leftarrow c+1\)
7end
8\(i \leftarrow i+1\)
9end
10return \(c\)
11end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines how many natural numbers between \(1\) and \(n\) are even, that is \(\lfloor n/2\rfloor\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm5, where \(n\) is the natural number given in input. Line 6 is executed only when \(i\) is even, that is \(\lfloor n/2\rfloor\) times. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\lfloor n/2\rfloor\)
    8 \(n\)
    10 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+1+(n+1)+n+\lfloor n/2\rfloor+n+1=3n+\lfloor n/2\rfloor+4. \]

    Since \(\frac{n-1}{2}\le\lfloor n/2\rfloor\le \frac{n}{2}\), we have \(\frac{7}{2}n+\frac{7}{2}\le S(n)\le \frac{7}{2}n+4\), hence \(S(n)=\Theta(n)\).

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+\lfloor n/2\rfloor+4=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm5, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.6: Running time (E6)

Consider the following algorithm, whose input is a natural number \(n\).

Algorithm: Algorithm 6

Input: A natural number \(n\)
Output: A natural number \(q\)
1function Algorithm6(n)
2\(q := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(q \leftarrow q+n\)
6\(i \leftarrow i+1\)
7end
8return \(q\)
9end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm adds \(n\) to \(q\) exactly \(n\) times, starting from \(q=0\): it determines \(n\cdot n=n^2\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm6, where \(n\) is the natural number given in input (there is only one input for each value of \(n\)). The body of the loop is executed \(n\) times and its condition \(n+1\) times:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    We now express the running time as a function of the input size. The input is the natural number \(n\), hence \(|I|=\Theta(\log_2 n)\), and \(S(n)=3n+4=\Theta(n)\). By rule (A) of the introduction to the exercises, there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{hence}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    The worst-case running time of Algorithm6, as a function of the input size \(|I|\), is \(T(|I|)=2^{\Theta(|I|)}\): it is exponential in \(|I|\), although the number of steps is linear in the value \(n\).

Exercise 12.7: Running time (E7)

Consider the following algorithm, whose input is an array \(a[1..n]\) of \(n\) integer numbers.

Algorithm: Algorithm 7

Input: An array \(a[1..n]\) of \(n\) integer numbers
Output: An integer number \(s\)
1function Algorithm7(a, n)
2\(s := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(a[i] > 0\) then
6\(s \leftarrow s+a[i]\)
7end
8\(i \leftarrow i+1\)
9end
10return \(s\)
11end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the sum of the positive values in the array \(a[1..n]\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm7 in the worst case, where \(n\) is the size of the array. The execution of line 6 depends on the input array. We define a function

    \[ t:\{1,2,\dots,n\}\to\{0,1\}, \]

    where \(t(i)=1\) if \(a[i]>0\), and \(t(i)=0\) otherwise. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\sum_{i=1}^{n}t(i)\)
    8 \(n\)
    10 \(1\)

    Therefore, the total number of steps is

    \[ 1+1+(n+1)+n+\sum_{i=1}^{n}t(i)+n+1=3n+4+\sum_{i=1}^{n}t(i). \]

    The worst possible case is when all entries are positive. Then \(t(i)=1\) for every \(i \in \{1,2,\dots,n\}\), and

    \[ S(n)=3n+4+\sum_{i=1}^{n}1=4n+4=\Theta(n). \]

    We now express the running time as a function of the input size. If all input values use a fixed constant number of bits, then \(|I|=\Theta(n)\), and \(S(n)=\Theta(n)\). By rule (B) of the introduction to the exercises (with \(k=1\)), there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{hence}\qquad T(|I|)=\Theta(|I|). \]

    The worst-case running time of Algorithm7, as a function of the input size \(|I|\), is \(T(|I|)=\Theta(|I|)\): it is linear in \(|I|\).

Exercise 12.8: Running time (E8)

Consider the following algorithm, whose input is an array \(a[1..n]\) of \(n\) integer numbers.

Algorithm: Algorithm 8

Input: An array \(a[1..n]\) of \(n\) integer numbers
Output: A natural number \(c\)
1function Algorithm8(a, n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(a[i] \bmod 2 = 0\) then
6\(c \leftarrow c+1\)
7end
8\(i \leftarrow i+1\)
9end
10return \(c\)
11end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the number of even values in the array \(a[1..n]\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm8 in the worst case, where \(n\) is the size of the array. The execution of line 6 depends on the input array. We define a function

    \[ t:\{1,2,\dots,n\}\to\{0,1\}, \]

    where \(t(i)=1\) if \(a[i] \bmod 2 = 0\), and \(t(i)=0\) otherwise. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\sum_{i=1}^{n}t(i)\)
    8 \(n\)
    10 \(1\)

    Therefore, the total number of steps is

    \[ 1+1+(n+1)+n+\sum_{i=1}^{n}t(i)+n+1=3n+4+\sum_{i=1}^{n}t(i). \]

    The worst possible case is when all entries are even. Then \(t(i)=1\) for every \(i \in \{1,2,\dots,n\}\), and

    \[ S(n)=3n+4+\sum_{i=1}^{n}1=4n+4=\Theta(n). \]

    We now express the running time as a function of the input size. If all input values use a fixed constant number of bits, then \(|I|=\Theta(n)\), and \(S(n)=\Theta(n)\). By rule (B) of the introduction to the exercises (with \(k=1\)), there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{hence}\qquad T(|I|)=\Theta(|I|). \]

    The worst-case running time of Algorithm8, as a function of the input size \(|I|\), is \(T(|I|)=\Theta(|I|)\): it is linear in \(|I|\).

Exercise 12.9: Running time (E9)

Consider the following algorithm, whose input is an array \(a[1..n]\) of \(n \ge 1\) integer numbers.

Algorithm: Algorithm 9

Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers
Output: An integer number \(m\)
1function Algorithm9(a, n)
2\(m := a[1]\)
3\(i := 2\)
4while \(i \leq n\) do
5if \(a[i] < m\) then
6\(m \leftarrow a[i]\)
7end
8\(i \leftarrow i+1\)
9end
10return \(m\)
11end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the minimum value in the array \(a[1..n]\).

  2. Let \(S(n)\) denote the number of steps executed by Algorithm9 in the worst case, where \(n\) is the size of the array. The body of the loop is executed for \(i=2,3,\dots,n\), that is \(n-1\) times. We define

    \[ t:\{2,3,\dots,n\}\to\{0,1\}, \]

    where \(t(i)=1\) if line 6 is executed at iteration \(i\), and \(t(i)=0\) otherwise. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n\)
    5 \(n-1\)
    6 \(\sum_{i=2}^{n}t(i)\)
    8 \(n-1\)
    10 \(1\)

    Therefore, the total number of steps is

    \[ 1+1+n+(n-1)+\sum_{i=2}^{n}t(i)+(n-1)+1=3n+1+\sum_{i=2}^{n}t(i). \]

    The worst possible case is when

    \[ a[1]>a[2]>\cdots>a[n]. \]

    Then \(t(i)=1\) for every \(i\in\{2,3,\dots,n\}\), and

    \[ S(n)=3n+1+\sum_{i=2}^{n}1=3n+1+(n-1)=4n=\Theta(n). \]

    We now express the running time as a function of the input size. If all input values use a fixed constant number of bits, then \(|I|=\Theta(n)\), and \(S(n)=\Theta(n)\). By rule (B) of the introduction to the exercises (with \(k=1\)), there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{hence}\qquad T(|I|)=\Theta(|I|). \]

    The worst-case running time of Algorithm9, as a function of the input size \(|I|\), is \(T(|I|)=\Theta(|I|)\): it is linear in \(|I|\).

Exercise 12.10: Running time (E10)

Consider the following algorithm, whose input is an array \(a[1..n]\) of \(n \ge 1\) integer numbers.

Algorithm: Algorithm 10

Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers
Output: true or false
1function Algorithm10(a, n)
2\(i := 1\)
3while \(i < n\) do
4if \(a[i]=a[i+1]\) then
5return true
6end
7\(i \leftarrow i+1\)
8end
9return false
10end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines whether the array contains two consecutive equal values: it returns true if \(a[i]=a[i+1]\) for some \(i\in\{1,2,\dots,n-1\}\), and false otherwise.

  2. Let \(S(n)\) denote the number of steps executed by Algorithm10 in the worst case, where \(n\) is the size of the array. If the first pair of consecutive equal values is found at iteration \(k\), the algorithm stops at line 5 after \(1+k+k+(k-1)+1=3k+1\le 3(n-1)+1\) steps. The worst possible case is therefore when no two consecutive values are equal: line 5 is never executed, and the algorithm checks all the \(n-1\) consecutive pairs. The number of times each line is executed in this case is:

    line number of executions
    2 \(1\)
    3 \(n\)
    4 \(n-1\)
    5 \(0\)
    7 \(n-1\)
    9 \(1\)

    Therefore, the total number of steps is

    \[ S(n)=1+n+(n-1)+(n-1)+1=3n=\Theta(n). \]

    (and \(3n>3(n-1)+1\), so this is indeed the worst case).

    We now express the running time as a function of the input size. If all input values use a fixed constant number of bits, then \(|I|=\Theta(n)\), and \(S(n)=\Theta(n)\). By rule (B) of the introduction to the exercises (with \(k=1\)), there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{hence}\qquad T(|I|)=\Theta(|I|). \]

    The worst-case running time of Algorithm10, as a function of the input size \(|I|\), is \(T(|I|)=\Theta(|I|)\): it is linear in \(|I|\).

Exercise 12.11: Running time (E11)

Consider the following algorithm, whose input is an array \(a[1..n]\) of \(n \ge 1\) integer numbers.

Algorithm: Algorithm 11

Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers
Output: A natural number \(c\)
1function Algorithm11(a, n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n-1\) do
5\(j := i+1\)
6while \(j \leq n\) do
7if \(a[i] < a[j]\) then
8\(c \leftarrow c+1\)
9end
10\(j \leftarrow j+1\)
11end
12\(i \leftarrow i+1\)
13end
14return \(c\)
15end

Questions

  1. What does the algorithm determine?

  2. Determine the worst-case running time of the algorithm.

Solution

  1. The algorithm determines the number of pairs of positions \((i,j)\), with \(1\leq i<j\leq n\), such that

    \[ a[i]<a[j]. \]

  2. Let \(S(n)\) denote the number of steps executed by Algorithm11 in the worst case, where \(n\) is the size of the array. The outer loop is executed for \(i=1,2,\dots,n-1\) (its condition is evaluated \(n\) times), and for each \(i\) the inner loop is executed for \(j=i+1,\dots,n\), that is \(n-i\) times (its condition is evaluated \(n-i+1\) times). Hence the body of the inner loop is executed once for every pair \((i,j)\) with \(1\le i<j\le n\), and the number of such pairs is

    \[ P=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}. \]

    We define \(t(i,j)=1\) if line 8 is executed for the pair \((i,j)\), and \(t(i,j)=0\) otherwise. The number of times each line is executed is:

    line number of executions
    2 \(1\)
    3 \(1\)
    4 \(n\)
    5 \(n-1\)
    6 \(\sum_{i=1}^{n-1}(n-i+1)=P+(n-1)\)
    7 \(P\)
    8 \(\sum_{1\le i<j\le n}t(i,j)\)
    10 \(P\)
    12 \(n-1\)
    14 \(1\)

    Therefore, the total number of steps is

    \[ 1+1+n+(n-1)+\big(P+(n-1)\big)+P+\sum_{1\le i<j\le n}t(i,j)+P+(n-1)+1=4n+3P+\sum_{1\le i<j\le n}t(i,j). \]

    The worst possible case for line 8 is when

    \[ a[1]<a[2]<\cdots<a[n]: \]

    then \(t(i,j)=1\) for every pair, and

    \[ S(n)=4n+4P=4n+2n(n-1)=2n^2+2n=\Theta(n^2). \]

    For example, for \(n=4\) and \(a[1..4]=(1,2,3,4)\) the algorithm returns \(c=6\) after \(S(4)=2\cdot 16+8=40\) steps.

    We now express the running time as a function of the input size. If all input values use a fixed constant number of bits, then \(|I|=\Theta(n)\), and \(S(n)=\Theta(n^2)\). By rule (B) of the introduction to the exercises (with \(k=2\)), there exist constants \(a_1,a_2,c_1,c_2>0\) such that, for all sufficiently large \(n\),

    \[ \frac{a_1}{c_2^{2}}\,|I|^2 \le S(n) \le \frac{a_2}{c_1^{2}}\,|I|^2, \qquad\text{hence}\qquad T(|I|)=\Theta(|I|^2). \]

    The worst-case running time of Algorithm11, as a function of the input size \(|I|\), is \(T(|I|)=\Theta(|I|^2)\): it is quadratic in \(|I|\).