10 Essential Iterative Problems for Mastering Time Complexity Analysis

Photo by Matthew Kwong on Unsplash

If you are like me and just started learning about algorithms, you may need more time to familiarize yourself with algorithm analysis. Below are 10 common problems to help you practice.

Table of Content:

· Single Loop
∘ Question 1
∘ Question 2
∘ Question 3
∘ Question 4
∘ Question 5
∘ Question 6
· Multiple loops
∘ Question 7 — Subsequent loops
∘ Question 8 — Nested loops
∘ Question 9 — Mixed loops
∘ Question 10 — Loops with different iterations

Find the running time of these programs:

Single Loop

Question 1

void sample_program(int n) {
  for (int i = 0; i < n; i++) {
    // Some Θ(1) operations
  }
}

Answer: The loop runs n times. Time complexity: Θ(n)

Question 2

void sample_program(int n) {
  for (int i = 0; i < n; i = i + c) { // c is a constant
  // Some Θ(1) operations
  }
}

Answer: Θ(n)

Explanation: Assuming the loop runs k times:

1st iteration: i = 0 * c

2nd iteration: i = 1 * c

3rd iteration: i = 2 * c

…

k-th iteration: i = (k-1) * c

Since i < n:

=> (k-1) * c < n

=> k < (n / c) + 1

Question 3

void sample_program (int n) {
  for (int i = n; i > 0; i = i - c) { // c is a constant
  // Some Θ(1) operations
  }
}

Answer: Θ(n)

Explanation: Similar explanation to question 2

Question 4

void sample_program (int n) {
  for (int i = 1; i < n; i = i * c) { // c is a constant
  // Some Θ(1) operations
  }
}

Answer: Θ(logn)

Explanation: Assuming the loop runs k times:

1st iteration: i = c⁰

2nd iteration: i = c¹

3rd iteration: i = c²

…

k-th iteration: i = c^(k-1)

Since i < n:

=> c^(k-1) < n

=> k < logc n + 1

Question 5

void sample_program (int n) {
  for (int i = n; i > 1; i = i/c) { // c is a constant
  // Some Θ(1) operations
  }
}

Answer: Θ(logn)

Explanation: similar explanation to question 4

Question 6

void sample_program (int n) {
  for (int i = 2; i < n; i = (i^c)) { // c is a constant
  // Some Θ(1) operations
  }
}

Answer: Θ(loglogn)

Explanation: Assuming the loop runs k times:

1st iteration: i = 2^(c⁰)

2nd iteration: i = 2^(c¹)

3rd iteration: i = 2^(c²)

…

k-th iteration: i = 2^(c^(k-1))

Since i < n:

=> 2^(c^(k-1)) < n

=> c^(k-1) < log2n

=> k < logc log2n + 1

Multiple loops

Question 7 — Subsequent loops

void sample_program(int n) {
  for (int i = 0; i < n; i ++) {
    // Some Θ(1) operations
  }
  
  for (int i = 1; i < n; i = i * 3) {
    // Some Θ(1) operations
  }
  
  for (int i = 1; i < 1000; i = i++) {
    // Some Θ(1) operations
  }
}

Answer: Θ(n)

Explanation: Since the program consists of 3 subsequent loops, the total running time = the sum of running time of 3 loops = Θ(n) + Θ(logn) + Θ(1)

Because we only care about the term with the highest growth rate in asymptotic notation, the overall time complexity of this program is Θ(n).

If you are unsure about the growth rates of different functions, please see the algorithm analysis cheat sheet I created in another post.

Question 8 — Nested loops

void sample_program(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j = j * 2) {
      // Some Θ(1) operations
    }
  }  
}

Answer: Θ(nlogn)

Explanation: The program consists of 2 nested loops. The running time of this program = the product of the running times of these 2 loops = Θ(n) * Θ(logn) = Θ(nlogn)

Question 9 — Mixed loops

void sample_program(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j = j * 3) {
      // Some Θ(1) operations
    }
  }

  for (int i = 0; i < n; i ++) {
    for (int j = 2; j < n; j ++) {
      // Some Θ(1) operations
    }
  } 
}

Answer: Θ(n²)

Explanation: The program consists of 2 subsequent nested loops. The running time of the program = the sum of the running time of these loops = Θ(nlogn) + Θ(n²)

Since n² is the higher-order growing term, the overall running time of the program is Θ(n²)

Question 10 — Loops with different iterations

void sample_program(int n, int m) {
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j = j * 3) {
      // Some Θ(1) operations
    }
  }

  for (int i = 0; i < m; i++) {
    for (int j = 1; j < m; j = j++) {
      // Some Θ(1) operations
    }
  }
}

Answer: Θ(nlogn + m²)

Explanation: The program consists of 2 subsequent nested loops, the running time of the program = sum of the running time of these 2 loops = Θ(nlogn) + Θ(m²)

Since n and m are two different inputs, we cannot tell which one is the higher-growing term, therefore, the running time of the program is Θ(nlogn + m²)

Reference: Most of these questions are inspired by the questions from GeeksforGeeks. Please check out the website for more details.

Subscribe to my Medium: https://medium.com/@exploreintellect/subscribe