2.2.1 Example 1: Linear Search

Linear search is a simple algorithm that searches for a target value within an array by iterating through the array's elements one by one. The time complexity of linear search can be analyzed as follows:

Python

def linear_search(arr, target):
for i in range(len(arr)):
    if arr[i] == target:
        return i
return -1

C++ Equivalent

int linear_search(int arr[], int target, int n) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

The algorithm's time complexity depends on the number of iterations in the for loop, which is determined by the length of the input array. In the worst-case scenario, the target value is not present in the array, and the algorithm must iterate through all of the array's elements. Therefore, the worst-case time complexity of linear search is $O(n)$, where n is the number of elements in the input array.

2.2.2 Example 2: Binary Search

Binary search is a more efficient search algorithm that operates on a sorted array. It repeatedly divides the search interval in half and compares the middle element of the interval to the target value. If the middle element is equal to the target, the search is successful; otherwise, the algorithm continues searching in the left or right subinterval, depending on whether the middle element is greater or smaller than the target value. The time complexity of binary search can be analyzed as follows:

Python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

C++ Equivalent

int binary_search(int arr[], int target, int n) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

The algorithm's time complexity depends on the number of iterations in the while loop. In each iteration, the search interval is divided in half, reducing the remaining search space by a factor of 2. The worst-case scenario occurs when the target value is not present in the array, requiring the algorithm to narrow the search interval until it becomes empty. In this case, the number of iterations required is $\log_2{n}$, where n is the number of elements in the input array. Therefore, the worst-case time complexity of binary search is $O(\log{n})$.

3.1.1 Example 1: Factorial Calculation

Factorial calculation is a classic problem that can be solved using both iterative and recursive approaches. We will analyze the space complexity of both approaches for calculating the factorial of a non-negative integer n.

Python

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
    result *= i

return result

C++ Equivalent

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

The iterative approach uses a single variable to store the intermediate results, and its memory requirements do not depend on the input size. Therefore, the space complexity of the iterative approach is $O(1)$, or constant space complexity.

Python

def factorial_recursive(n):
    if n == 0:
        return 1
    else:
        return n * factorial_recursive(n - 1)

C++ Equivalent

int factorial_recursive(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial_recursive(n - 1);
    }
}

The recursive approach uses the call stack to store the intermediate results, and the depth of the call stack is determined by the input size. In this case, the space complexity is equal to the maximum depth of the call stack, which is n. Therefore, the space complexity of the recursive approach is $O(n)$, or linear space complexity.

3.1.2 Example 2: Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that recursively divides the input array into two halves, sorts the halves individually, and then merges the sorted halves to produce the final sorted array. The space complexity of merge sort can be analyzed as follows:

Python

def merge_sort(arr):
      if len(arr) <= 1:
          return arr
  
      mid = len(arr) // 2
      left = merge_sort(arr[:mid])
      right = merge_sort(arr[mid:])
  
      return merge(left, right)
  
  def merge(left, right):
      result = []
      i = j = 0
  
      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              result.append(left[i])
              i += 1
          else:
              result.append(right[j])
              j += 1
  
      result.extend(left[i:])
      result.extend(right[j:])
  
      return result
  

C++ Equivalent

#include <iostream>
#include <vector>

using namespace std;

vector<int> merge(vector<int> left, vector<int> right) {
    vector<int> result;
    int i = 0, j = 0;

    while (i < left.size() && j < right.size()) {
        if (left[i] < right[j]) {
            result.push_back(left[i]);
            i++;
        }
        else {
            result.push_back(right[j]);
            j++;
        }
    }

    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }

    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }

    return result;
}

vector<int> merge_sort(vector<int> arr) {
    if (arr.size() <= 1) {
        return arr;
    }

    int mid = arr.size() / 2;

    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

int main() {
    vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };
    vector<int> sorted_arr = merge_sort(arr);

    for (int i = 0; i < sorted_arr.size(); i++) {
        cout << sorted_arr[i] << " ";
    }
    cout << endl;

    return 0;
}

The space complexity of merge sort depends on the memory required to store the intermediate results during the merge step. In the worst case, the algorithm needs to allocate an additional array with the same size as the input array to store the merged results. In this case, the space complexity is proportional to the input size, n. Therefore, the worst-case space complexity of merge sort is $O(n)$, or linear space complexity.

4.1.1 Example 1: Dynamic Array

Consider a dynamic array, which is a data structure that allows elements to be added or removed and automatically resizes itself as needed. The resizing operation can be expensive, as it may involve allocating a new block of memory and copying elements from the old array to the new one. However, the resizing operation occurs infrequently, and most other operations, such as adding or removing elements, have constant time complexity. We can use amortized analysis to determine the average cost of performing a sequence of operations on a dynamic array.

Suppose that we start with an empty dynamic array and perform n insertions. Each time the array is full, we double its size. This resizing operation occurs when the array has 1, 2, 4, 8, ..., $2^k$ elements, where $2^k \le n$. The total cost of these resizing operations is:

$$1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 \le 2n - 1$$

Therefore, the amortized cost of performing n insertions is:

$$\frac{2n - 1}{n} = 2 - \frac{1}{n}$$

Since the amortized cost is constant for a large number of insertions, the overall performance of the dynamic array is efficient, despite the occasional expensive resizing operations.

4.2.1 Example 1: Fibonacci Numbers

The Fibonacci sequence is a classic example of a problem that can be solved using dynamic programming. The naive recursive implementation of the Fibonacci sequence has exponential time complexity due to the repeated computation of overlapping subproblems. By using dynamic programming, we can significantly improve the time complexity of the algorithm.

Python

def fibonacci_dp(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
fib[1] = 1

for i in range(2, n + 1):
    fib[i] = fib[i - 1] + fib[i - 2]

return fib[n]

C++ Equivalent

int fibonacci_dp(int n) {
    if (n <= 1) {
        return n;
    }
    int fib[n + 1];
    memset(fib, 0, sizeof(fib));
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

The dynamic programming implementation of the Fibonacci sequence has a time complexity of $O(n)$ and a space complexity of $O(n)$. By eliminating redundant computation, we have significantly reduced the time complexity at the cost of additional memory.

4.2.2 Example 2: Longest Common Subsequence

The longest common subsequence (LCS) problem is another example that can be solved using dynamic programming. Given two sequences, the LCS problem asks to find the length of the longest subsequence that is common to both sequences. The naive approach to solving the LCS problem involves generating all subsequences of both sequences and comparing them, which has exponential time complexity. By using dynamic programming, we can significantly improve the time complexity of the algorithm.

Python

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    L = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
    for j in range(n + 1):
        if i == 0 or j == 0:
            L[i][j] = 0
        elif X[i - 1] == Y[j - 1]:
            L[i][j] = L[i - 1][j - 1] + 1
        else:
            L[i][j] = max(L[i - 1][j], L[i][j - 1])

return L[m][n]

C++ Equivalent

#include <iostream>
#include <cstring>
using namespace std;

int longest_common_subsequence(string X, string Y) {
    int m = X.length(), n = Y.length();
    int L[m + 1][n + 1];
    memset(L, 0, sizeof(L));

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    return L[m][n];
}

int main() {
    string X = "ABCDGH";
    string Y = "AEDFHR";
    cout << longest_common_subsequence(X, Y) << endl;
    return 0;
}

The dynamic programming implementation of the longest common subsequence problem has a time complexity of $O(mn)$ and a space complexity of $O(mn)$, where m and n are the lengths of the input sequences. By exploiting the problem's optimal substructure and overlapping subproblems, we have significantly reduced the time complexity at the cost of additional memory.