Algorithm Analysis - Tran Ba Tuan - HUS - VNU

(1) What is Algorithm Complexity

Algorithm complexity refers to the computational resources an algorithm requires to solve a problem, typically in terms of time and space. It is usually analyzed based on:

Time Complexity: This measures the amount of time an algorithm takes as a function of the input size (denoted as n). The time complexity is expressed using Big-O notation, which describes the upper bound of the running time. Common complexities include:

• $O(1):$ Constant time
• $O(log n):$ Logarithmic time
• $O(n):$ Linear time
• $O(n log n):$ Linearithmic time
• $O(n²):$ Quadratic time
• $O(2^n):$ Exponential time
• $O(n!):$ Factorial time

Space Complexity: This measures the amount of memory an algorithm uses relative to the input size. It is also expressed in Big-O notation, capturing how additional memory grows as input size increases.

Efficient algorithms strive for low time and space complexity, ensuring scalability and performance when dealing with larger datasets.

(2) Examples: Upper bound

Example 1. What is the Upper bound for:

a, We are given the function:

$$f(n) = 3n + 5$$

Block

• As $n$ increases, the linear term $3n$ dominates the constant $5$.
• The constant $3$ in front of $n$ can be ignored because Big-O notation focuses on the order of growth, not constant factors.
• Answer: $O(f(n)) = O(n)$

b, We are given the function:

$$f(n) = 4n^2 + 3$$

Block

• As $n$ increases, the quadratic term $4n^2$ dominates the constant $3$.
• The coefficient $4$ can be ignored in Big-O notation.
• Answer: $O(f(n)) = O(n^2)$

c, We are given the function:

$$f(n) = n^4 + 100n^2 + 80$$

Block

• As $n$ increases, the term $n^4$ grows faster than $100n^2$ and $80$, so it dominates the function.
• The coefficients $100$ and $80$ are constants and can be ignored.
• Answer: $O(f(n)) = O(n^4)$

d, We are given the function:

$$f(n) = 5n^3 - 5n^2$$

Block

• As $n$ increases, the cubic term $5n^3$ dominates the quadratic term $-5n^2$.
• The coefficient $5$ can be ignored in Big-O notation.
• Answer: $O(f(n)) = O(n^3)$

e, We are given the function:

$$f(n) = 502$$

Block

• This is a constant function; it does not depend on $n$ and remains the same regardless of input size.
• For constant functions, the upper bound is $O(1)$, meaning the function has constant time complexity.
• Answer: $O(f(n)) = O(1)$

(2) Examples: Time complexity

General question: What is the time complexity?

Example 2. Calculate $S$:

$$S = \frac{n(n-1)}{2}$$

Block

• This is kind of a trick question. This is ONE independent operation, no loops involved, and the actual value of $n$ does not matter, so It has a time complexity of $O(1)$
• Time Complexity: $O(1)$

Example 3.

for i in range(0, n):
    print('Current Number', i)

• The loop runs from $0$ to $n - 1$, so the number of iterations is $n$, and there is a single print operation per iteration.
• Time Complexity: $O(n)$

Example 4.

for i in range(0, n):
    print('Current Number', i)
    break

• The loop seems to be similar to Example 3., but there is a break statement right after the very first operation. Therefore, the loop will be terminated on the very first iteration.
• Time Complexity: $O(1)$

Example 5.

def function(n):
    i = 1
    while i <= n:
        i = i * 2
        print(i)
function(100)

• In this function, there is a loop running from $i = 1$ to $n$. However, inside the loop itself, the value of $i$ doubles with each iteration, so the number of iterations is logarithmic with respect to $n$.
• Time Complexity: $O(log(n))$

Example 6.

for i in range(0, n):
    for j in range(0, n):
        print("Value of i, j", i, j)

• In this case, we can clearly see that there are two loops, each going from $0$ to $n - 1$, so there are $n \times n = n^2$ total iterations.
• Time Complexity: $O(n^2)$

Example 7.

public void function(int n) {
    int i, j, k, count = 0;
    for(i = n/2; i <= n; i++)
        for(j = 1; j + n/2 <= n; j++)
            for(k = 1; k <= n; k = k * 2)
                count++;
}

• The outer loop runs from $i = n/2$ to $n$, so it executes $n/2$ times, which is $O(n)$.
• The middle loop runs $n/2$ times.
• The innermost loop doubles $k$ each time, so it runs $O(log(n))$ times.
• The total time complexity is the product of all three loops:

• Time Complexity: $O(n^2log(n))$

Example 8.

public void function(int n) {
    int i, j, k, count = 0;
    for(i = n/2; i <= n; i++)
        for(j = 1; j <= n; j = 2 * j)
            for(k = 1; k <= n; k = k * 2)
                count++;
}

• The outer loop runs from $i = n/2$ to $n$, so it executes $n/2$ times, which is $O(n)$.
• The middle loop doubles $j$ each time, so it runs $O(log(n))$ times.
• The innermost loop doubles $k$ each time, so it runs $O(log(n))$ times.
• The total time complexity is the product of all three loops:

• Time Complexity: $O(n log^2(n))$

(3) Practice: Time complexity

Exercise 1. What is the algorithm complexity?

a, We are given the function:

$$T(n) = nlogn + 3n + 2$$

Block

• We have three terms: $nlogn$, $3n$, and $2$.
• The dominant term is $nlogn$ as it grows faster than $n$ for large values of $n$.
• The constant terms and lower-order terms ($ 3n $ and $ 2 $) are dropped in Big O notation.
• Therefore, the complexity is $O(n log(n))$.
• Answer: $O(n log(n))$

b, We are given the function:

$$T(n) = nlog(n!) + 5n^2 + 7$$

Block

• We have three terms here: $nlog(n!)$, $5n^2$, and $7$.
• Note that $log(n!)$ is $O(n log n)$ (this is a mathematical fact).
• So, $nlog(n!)$ is actually $O(n^2 log n)$.
• However, for very large $n$, $n^2$ grows faster than $n^2 log n$.
• The constant terms (5 and 7) are dropped in Big O notation.
• Therefore, the overall time complexity is dominated by $n^2$, giving us $O(n^2)$.
• Answer: $O(n^2)$

c, We are given the function:

$$T(n) = 1000n + 0.01n^2$$

Block

• We have two terms: $1000n$ and $0.01n^2$.
• Although $1000n$ has a larger coefficient, $n^2$ grows much faster for large values of $n$.
• In Big O notation, we’re concerned with the growth rate for large $n$, not the coefficients.
• Therefore, $n^2$ dominates, and the time complexity is $O(n^2)$.
• Answer: $O(n^2)$

d, We are given the function:

$$T(n) = 100nlogn + n^3 + 100n$$

Block

• We have three terms: $100nlogn$, $n^3$, and $100n$.
• For large values of $n$, $n^3$ grows much faster than both $nlogn$ and $n$.
• The constants (100) are dropped in Big O notation.
• Therefore, the time complexity is dominated by $n^3$, giving us $O(n^3)$.
• Answer: $O(n^3)$

e, We are given the function:

$$T(n) = 0.01nlogn + n(logn)^2$$

Block

• We have two terms: $0.01nlogn$ and $n(logn)^2$.
• $n(logn)^2$ grows faster than $nlogn$ for large $n$.
• The constant (0.01) is dropped in Big O notation.
• Therefore, the time complexity is $O(n log^2 n)$.
• Answer: $O(n log^2 n)$

Exercise 2. What is the time complexity?

a, Given method:

// Returns the sum of the integers in given array .
public static int example1(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n; j++) // loop from 0 to n -1
        total += arr[j];
    return total;
}

• This function has a single loop that iterates from $0$ to $n-1$.
• The number of iterations is directly proportional to the size of the input array $(n)$.
• Each iteration performs a constant-time operation (addition).
• Therefore, the time complexity is linear, $O(n)$.
• Answer: $O(n)$

b, Given method:

// Returns the sum of the integers with even index in given array .
public static int example2(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n; j += 2) // note the increment of 2
        total += arr [j];
    return total;
}

• This function has a loop that iterates over every other element of the array.
• Although it processes only half of the elements, in Big O notation, we still consider this linear time.
• The number of operations is still directly proportional to $n$, just with a factor of (1/2).
• Constants are dropped in Big O notation, so $O(n/2)$ simplifies to $O(n)$.
• Answer: $O(n)$

c, Given method:

// Returns the sum of the prefix sums of given array .
public static int example3(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n ; j++) // loop from 0 to n -1
        for (int k = 0; k <= j; k++) // loop from 0 to j
            total += arr [j];
    return total;
}

• This function has two nested loops.
• The outer loop runs $n$ times.
• For each iteration of the outer loop, the inner loop runs $j + 1$ times, where $j$ goes from $0$ to $n-1$.
• The total number of iterations is the sum of integers from $1$ to $n$, which is $n(n+1)/2$.
• This simplifies to $O(n^2)$ in Big O notation.
• Answer: $O(n^2)$

d, Given method:

// Returns the sum of the prefix sums of given array .
public static int example4(int[] arr) {
    int n = arr.length, prefix = 0, total = 0;
    for (int j = 0; j < n; j++) { // loop from 0 to n -1
        prefix += arr [j];
        total += prefix;
    }
    return total;
}

• This function has a single loop that iterates $n$ times.
• Inside the loop, all operations (addition and assignment) are constant time.
• Although it’s calculating prefix sums, it does so efficiently in a single pass through the array.
• Therefore, the time complexity is linear, $O(n)$
• Answer: $O(n)$

e, Given method:

// Returns the number of times second array stores sum of prefix sums from first
public static int example5(int[] first, int[] second) {
    // assume equal - length arrays
    int n = first.length, count = 0;
    for (int i = 0; i < n; i++) { // loop from 0 to n -1
        int total = 0;
        for (int j = 0; j < n; j++) // loop from 0 to n -1
            for (int k = 0; k <= j; k++) // loop from 0 to j
                total += first [k];
                if (second [i] == total) count++;
    }
    return count;
}

• This function has three nested loops.
• The outermost loop runs $n$ times.
• For each iteration of the outer loop, the middle loop runs $n$ times.
• For each iteration of the middle loop, the innermost loop runs $j + 1$ times, where $j$ goes from $0$ to $n-1$.
• The total number of iterations is approximately $n * n * (n/2) = n^3/2$.
• In Big O notation, this simplifies to $O(n^3)$.
• Answer: $O(n^3)$

(4) Practice: Master theorem

(Master theorem) If $n$ is a power of $b$, the solution to the recurrence:

$$T(n) = \begin{cases} aT(n/b) + n^d & \text{if } n > 1 \text{ and } a \geq 1, b > 1, d \geq 0 \quad \\ 1 & \text{if } n \leq 1\end{cases}$$

Block

is denoted:

$$T(n) = \begin{cases} O(n^d) & \text{if } a < b^d \\ O(n^d \log(n)) & \text{if } a = b^d \\ O(n^{\log_b(a)}) & \text{if } a > b^d \end{cases}$$

Block

Example 9. Determine algorithm complexity of this expression:

$$T(n) = \begin{cases} 2T(n-1) - 1 & \text{if } n > 0 \\ 1 & \text{otherwise} \end{cases}$$

Block

\begin{flalign*} &\text{Let: } T(n-1) = 2T(n-2) - 1 \\ &\Rightarrow T(n) = 2(2T(n-2) - 1) - 1 \qquad (1) \quad\\ &= 4T(n-2) - 3 \\[10pt] &\text{Let: } T(n-2) = 2T(n-3) - 1 \\ &\Rightarrow T(n) = 8T(n-3) - 7 \qquad (2)\\[10pt] &\text{From (1), (2): } \\ &T(n) = 2^k T(n-k)-(2^k - 1) \\[10pt] &\text{Let k = n: } \\ &T(n) = 2^n T(0) - (2^n - 1) \\ &= 2^n . 1 - (2^n - 1) = 2^n - 2^n + 1 = 1 \\[10pt] &\Rightarrow T(n) = O(1) \\ \end{flalign*}

Block

Example 10. Determine algorithm complexity of this expression:

$$T(n) = \begin{cases} 3T(n-1) & \text{if } n > 0 \\ 1 & \text{otherwise} \end{cases}$$

Block

\begin{flalign*} &\text{Let: } T(n-1) = 3T(n-2) \\ &\Rightarrow T(n) = 3(3T(n-2)) = 3^2 T(n-2) \qquad (1) \quad \\[10pt] &\text{Let: } T(n-2) = 3T(n-3) \\ &\Rightarrow T(n) = 3^3 T(n-3) \qquad (2) \quad \\[10pt] &\text{From (1), (2): } \\ &T(n) = 3^k T(n-k) \\[10pt] &\text{Let k = n: } \\ &T(n) = 3^n T(0) = 3^n \\[10pt] &\Rightarrow T(n) = O(3^n) \\ \end{flalign*}

Block

Example 11. Determine algorithm complexity:

1. Given expression:

$$T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=2T(n/2)+6n−1 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=2 ;\quad b=2 ;\quad d=1; \\ & \text{We see that } 2 = 2^1 \text{ or } a = b^d \\ & \text{Therefore this is case 2 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(nlog(n)) \\ \end{flalign*}

Block

2. Given expression:

$$T(1)=2, \text{and for all } n≥2 \text{ a power of 3 }, T(n)=4T(n/3)+3n−5 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=4 ;\quad b=3 ;\quad d=1; \\ & \text{We see that } 4 > 3^1 \text{ or } a > b^d \\ & \text{Therefore this is case 3 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_3 4}) \\ \end{flalign*}

Block

3. Given expression:

$$T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n^2−n \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3 ;\quad b=2 ;\quad d=2; \\ & \text{We see that } 3 < 2^2 \text{ or } a < b^d \\ & \text{Therefore this is case 1 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^2) \\ \end{flalign*}

Block

Exercise 3. Determine algorithm complexity:

1. Given expression:

$$T(1)=1, \text{and for all } n≥2, T(n)=3T(n-1)+2 \quad$$

Block

1. Let $T(n-1)=3 T(n-2)+2$

   $$\begin{aligned} T(n)= & 3(3 T(n-2)+2)+2=3^2 T(n-2)+3 \cdot 2+2 \quad\\ &=3^2 T(n-2)+6+2=3^2 T(n-2)+8 \end{aligned}$$

   Block

2. Let $T(n-2)=3 T(n-3)+2$

   $$\begin{aligned} T(n)= & 3^2(3 T(n-3)+2)+8=3^3 T(n-3)+3^2 \cdot 2+8 \quad\\ & =3^3 T(n-3)+18+8=3^3 T(n-3)+26 \end{aligned}$$

   Block

3. Generalizing, let $k$ be the number of steps:

   $$T(n)=3^k T(n-k)+2 \cdot\left(3^{k-1}+3^{k-2}+\ldots+1\right) \quad$$

   Block

The summation $2 \cdot\left(3^{k-1}+3^{k-2}+\ldots+1\right)$ is a geometric series:

$$=2 \cdot \frac{3^k-1}{3-1}=2 \cdot \frac{3^k-1}{2}=3^k-1 \quad$$

Block

Thus, $T(n)=3^k T(n-k)+\left(3^k-1\right)$

1. Let $k=n-1$ :

   $$\begin{gathered} T(n)=3^{n-1} T(1)+\left(3^{n-1}-1\right)=3^{n-1} \cdot 1+\left(3^{n-1}-1\right) \quad \\ =3^{n-1}+3^{n-1}-1=2 \cdot 3^{n-1}-1 \end{gathered}$$

   Block

2. Final result:

   $$T(n)=2 \cdot 3^{n-1}-1$$

   Block

Thus, $T(n)=O\left(3^n\right)$.

2. Given expression:

$$T(1)=3, \text{and for all } n≥2, T(n)=T(n-1)+2n−3 \quad$$

Block

1. Let $T(n-1)=T(n-2)+2(n-1)-3$

   $$T(n)=T(n-2)+2(n-1)-3+2 n-3=T(n-2)+2 n-2 \quad$$

   Block

2. Let $T(n-2)=T(n-3)+2(n-2)-3$

   $$\begin{gathered} T(n)=T(n-3)+2(n-2)-3+2 n-2 \\ =T(n-3)+2 n-2+2(n-2)-3=T(n-3)+2 n-2+2 n-4-3=T(n-3)+4 n-9 \quad \end{gathered}$$

   Block

3. Generalizing:

   $$T(n)=T(n-k)+2 n-2+2(n-1)-3+2(n-2)-3+\ldots+2(n-k+1)-3 \quad$$

   Block

Let’s compute the contributions from the summation:

$$T(n)=T(n-k)+(2 n-2)+(2 n-4)+\ldots \quad$$

Block

The series has $k$ terms:

$$=T(n-k)+2 n \cdot k-3 k-2=T(n-k)+2 n k-3 k-2 \quad$$

Block

1. Let $k=n-1$ :

   $$\begin{gathered} T(n)=T(1)+2(n-1)(n-1)-3(n-1)-2 \\ =3+2(n-1)^2-3(n-1)-2 \\ =3+2\left(n^2-2 n+1\right)-3 n+3-2=2 n^2-7 n+4 \quad \end{gathered}$$

   Block

2. Final result:

   $$T(n)=2 n^2-7 n+4$$

   Block

Thus, $T(n)=O\left(n^2\right)$.

3. Given expression:

$$T(1)=1, \text{and for all } n≥2, T(n)=2T(n-1)+n−1 \quad$$

Block

1. Let $T(n-1)=2 T(n-2)+(n-2)$

   $$\begin{gathered} T(n)=2(2 T(n-2)+(n-2))+(n-1)=2^2 T(n-2)+2(n-2)+n-1 \quad \\ =2^2 T(n-2)+2 n-4+n-1=2^2 T(n-2)+3 n-5 \end{gathered}$$

   Block

2. Let $T(n-2)=2 T(n-3)+(n-3)$

   $$\begin{gathered} T(n)=2^2(2 T(n-3)+(n-3))+3 n-5 \\ =2^3 T(n-3)+2^2(n-3)+3 n-5=2^3 T(n-3)+4(n-3)+3 n-5 \quad\\ =2^3 T(n-3)+4 n-12+3 n-5=2^3 T(n-3)+7 n-17 \end{gathered}$$

   Block

3. Generalizing:

   $$T(n)=2^k T(n-k)+\sum_{j=0}^{k-1} 2^j \cdot(n-j-1) \quad$$

   Block

This simplifies to:

$$T(n)=2^k T(n-k)+(\text { a summation }) \quad$$

Block

1. Let $k=n-1$ :

   $$T(n)=2^{n-1} T(1)+\sum_{j=0}^{n-2} 2^j(n-j-1) \quad$$

   Block

The sum contributes:

$$=2^{n-1} \cdot 1+n\left(2^{n-1}-1\right)-\left(2^{n-1}-1\right)=2^{n-1}+n \cdot 2^{n-1}-2^{n-1}+1=(n-1) \cdot 2^{n-1}+1 \quad$$

Block

1. Final result:

   $$T(n)=(n-1) \cdot 2^{n-1}+1$$

   Block

Thus, $T(n)=O\left(2^n\right)$.

4. Given expression:

$$T(1)=5, \text{and for all } n≥2, T(n)=2T(n-1)+3n+1 \quad$$

Block

1. Let $T(n-1)=2 T(n-2)+3(n-1)+1$

   $$\begin{gathered} T(n)=2(2 T(n-2)+3(n-1)+1)+3 n+1 \\ =2^2 T(n-2)+2(3(n-1)+1)+3 n+1=2^2 T(n-2)+6 n-6+2+3 n+1 \quad \\ =2^2 T(n-2)+9 n-3 \end{gathered}$$

   Block

2. Let $T(n-2)=2 T(n-3)+3(n-2)+1$

   $$\begin{gathered} T(n)=2^2(2 T(n-3)+3(n-2)+1)+9 n-3 \\ =2^3 T(n-3)+2^2(3(n-2)+1)+9 n-3 \\ =2^3 T(n-3)+12 n-24+4+9 n-3=2^3 T(n-3)+21 n-23 \quad \end{gathered}$$

   Block

3. Generalizing:

   $$T(n)=2^k T(n-k)+\sum_{j=0}^{k-1} 2^j(3(n-j)+1) \quad$$

   Block

4. Let $k=n-1$ :

   $$T(n)=2^{n-1} T(1)+\sum_{j=0}^{n-2} 2^j(3(n-j)+1) \quad$$

   Block

Expanding the summation:

$$=2^{n-1} \cdot 5+\sum_{j=0}^{n-2}\left(3 n \cdot 2^j-3 j \cdot 2^j+2^j\right) \quad$$

Block

1. Final result: Evaluating the terms yields:

   $$T(n)=5 \cdot 2^{n-1}+3 n\left(2^{n-1}-1\right)+\left(2^{n-1}-1\right)=5 \cdot 2^{n-1}+3 n \cdot 2^{n-1}-3 n+2^{n-1}-1 \quad$$

   Block

Simplifying,

$$=(5+3 n+1) 2^{n-1}-3 n-1=(3 n+6) 2^{n-1}-3 n-1 \quad$$

Block

Thus, $T(n)=O\left(2^n\right)$

5. Given expression:

$$T(1)=4, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=2T(n/2)+3n+2 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=2; \quad b=2; \quad d=1; \\ & \text{We see that } 2 = 2^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}

Block

6. Given expression:

$$T(1)=1, \text{and for all } n≥2 \text{ a power of 6 }, T(n)=6T(n/6)+2n+3 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=6; \quad b=6; \quad d=1; \\ & \text{We see that } 6 = 6^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}

Block

7. Given expression:

$$T(1)=3, \text{and for all } n≥2 \text{ a power of 6 }, T(n)=6T(n/6)+3n−1 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=6; \quad b=6; \quad d=1; \\ & \text{We see that } 6 = 6^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}

Block

8. Given expression:

$$T(1)=3, \text{and for all } n≥2 \text{ a power of 3 }, T(n)=4T(n/3)+2n−1 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=4; \quad b=3; \quad d=1; \\ & \text{We see that } 4 > 3^1 \text{ or } a > b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_3 4}) \\ \end{flalign*}

Block

9. Given expression:

$$T(1)=4, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n^2−2n+1 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3; \quad b=2; \quad d=2; \\ & \text{We see that } 3 < 2^2 \text{ or } a < b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^2) \\ \end{flalign*}

Block

10. Given expression:

$$T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n−2 \quad$$

Block

\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3; \quad b=2; \quad d=1; \\ & \text{We see that } 3 > 2^1 \text{ or } a > b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_2 3}) \\ \end{flalign*}

Block