Analysis of Iterative Algorithms

Reading Time: 3 minutes

Iterative algorithms are the most common classes of algorithms. They are easy to implement and analyze. In the next sections, we review the skeletons of the most common iterative algorithms.

Quadratic Complexity

Case 1: When Inner Loop Starts from Beginning

func doSomething(n: Int) {
  var a: Int, b: Int
  a = 1
  while a <= n {
    b = 1
    while b <= n {
      // Do Some Θ(1) Operations
      b += 1
    }
    a += 1
  }
}

The total number of Θ(1) operations that will be executed can be summarized as:

When $a=$$1,$$2,$$3,$$\cdots,$$n$∴ Total Θ(1) Operations
inner loop will run$n$ times$n$ times$n$ times$\cdots,$$n$ times$(n*n)$ times
Suppose $n=8$, then inner loop runs$8$ times$8$ times$8$ times$\cdots,$$8$ times$64$ times

∴ Ignoring all the lower order terms and coefficients, the worst-case running time is, $T(n) = \Theta(n^2)$.

Case 2: When Inner Loop Starts From Outer Loop Variable

func doSomething(n: Int) {
  var a: Int, b: Int
  a = 1
  while a <= n {
    b = a
    while b <= n {
      // Do Some Θ(1) Operations
      b += 1
    }
    a += 1
  }
}

The total number of Θ(1) operations that will be executed can be summarized as:

when $a=$$1,$$2,$$3,$$\cdots,$$n$∴ Total Θ(1) Operations
inner loop will run$n$ times$n-1$ times$n-2$ times$\cdots,$$1$ time$\sum_{i=1}^n i$ times
Suppose $n=8$, then inner loop runs$8$ times$7$ times$6$ times$\cdots,$$1$ time$36$ times

∴ Ignoring all the lower order terms and coefficients, the worst-case running time would still be, $T(n) = \Theta(n^2)$.

Quasilinear Complexity

func doSomething(n: Int) {
  var a: Int, b: Int
  a = 1
  while a <= n {
    b = 1
    while b < n {
      // Do Some Θ(1) Operations
      b *= 2
    }
    a += 1
  }
}
when $a=$$1,$$2,$$3,$$\cdots,$$n$∴ Total Θ(1) Operations
inner loop will run$\lg n$ times$\lg n$ times$\lg n$ times$\cdots,$$\lg n$ time$n*\lg n$ times
Suppose $n=8$, then inner loop runs$3$ times$3$ times$3$ times$\cdots,$$3$ times$24$ times

∴ Ignoring all the lower order terms and coefficients, the worst-case running time is, $T(n) = \Theta(n \lg n)$.

Linear Complexity

func doSomething(n: Int) {
  var a = 1
  while a <= n {
    // Do Some Θ(1) Operations
    a += 1
  }
}

The total number of Θ(1) operations that will be executed can be summarized as:

When $a=$$1,$$2,$$3,$$\cdots,$$n$∴ Total Θ(1) Operations
Θ(1) operations will run$1$ time$1$ time$1$ time$\cdots,$$1$ time$(1*n)$ times
Suppose $n=8$, then Θ(1) operations run$1$ time$1$ time$1$ time$\cdots,$$1$ time$8$ times

∴ Ignoring all the coefficients, the worst-case running time is, $T(n) = \Theta(n)$.

Logarithmic Complexity

func doSomething(n: Int) {
  var a = 1
  while a < n {
    // Do Some Θ(1) Operations
    a *= 2
  }
}

The total number of Θ(1) operations that will be executed can be summarized as:

when $a=$$1,$$2,$$4,$$\cdots,$$n$∴ Total Θ(1) Operations
Θ(1) operations will run$1$ time$1$ time$1$ time$\cdots,$$1$ time$(1*\lg n)$ times
Suppose $n=8$, then Θ(1) operations run$1$ time$1$ time$1$ time$3$ times

∴ Ignoring all the coefficients, the worst-case running time is, $T(n) = \Theta(\lg n)$.

Constant Complexity

func doSomething() {
  let n = 8
  var a = 1
  while a < n {
    // Do Some Θ(1) Operations
    a += 1
  }
}

In general, when $n$ is constant, the running time is considered as, $T(n) = \Theta(1)$.