Brief overview of algorithm complexity

As we saw earlier, you can think of the efficiency of your code in two different ways - time complexity (how long it takes to run) and space complexity (how much memory it uses). These two concepts are not necessarily correlated.

Let’s see a few examples, which will also help us understand how you can make your code more efficient.

Reducing both memory and time

Problem: how to compute the maximum product of numeric values in two vectors?

A naive solution:

x <- c(1, 2, 3, 4)
y <- c(7, 1, 4, 3)
# loop over all combinations of x and y; store the output
out <- rep(NA, length(x)*length(y))
pos <- 1
for (i in x){
  for (j in y){
    out[pos] <- i * j
    pos <- pos + 1
  }
}
# then compute the max
max(out)
## [1] 28

A solution with lower time and memory complexity:

# compute the max of x and y
max_x <- max(x)
max_y <- max(y)
# then the product
max_x * max_y
## [1] 28

Why lower time? Because we don’t have to compute n \(\times\) m products; only 1. Why lower memory? Because we don’t need to create a new vector of size n \(\times\) m to store all the products.

Reducing memory without changing time

Problem: how to compute the total sum of numbers in the fibonacci sequence up to position n?

A naive solution:

n <- 20
fib <- rep(NA, n)
fib[1:2] <- c(0, 1) # initialize fib sequence
for(i in 3:n) {
  fib[i] <- fib[i-1] + fib[i-2]
}
sum(fib)
## [1] 10945

A solution with lower memory complexity but same time:

n <- 20
first_number <- 0
second_number <- 1
running_sum <- first_number + second_number
i <- 2 # how many numbers we have counted so far
while (i < n){
  # computing i_th number in sequence
  new_number <- first_number + second_number
  # adding to running sum
  running_sum <- running_sum + new_number
  # computing new numbers for next iteration
  first_number <- second_number
  second_number <- new_number
  # increasing iteration count by 1
  i <- i + 1
}
running_sum
## [1] 10945

Reducing time without changing memory

Problem: how to find all the pairs of integers in an unsorted vector that sum up to a given number S? (For simplicity, assume an integer can also be paired up with itself.)

A naive solution:

x <- c(1, 2, 3, 4, 5)
S <- 5
pairs <- list()
pos <- 0 # number of pairs found
for (i in x){
  for (j in x){
    if (i+j==S){ # for each combination of i,j - check if sum is S
      pos <- pos + 1
      pairs[[pos]] <- c(i, j)
    }
  }
}
pairs
## [[1]]
## [1] 1 4
## 
## [[2]]
## [1] 2 3
## 
## [[3]]
## [1] 3 2
## 
## [[4]]
## [1] 4 1

A solution with lower time but same memory:

x <- c(1, 2, 3, 4, 5)
S <- 5
pairs <- list()
pos <- 0 # number of pairs found
for (i in x){
  # for each value in x, find number that would add up to S
  diff <- S - i
  # if value is in x, then keep the pair
  if (diff %in% x){
    pos <- pos + 1
    pairs[[pos]] <- c(i, diff)
  }
}
pairs
## [[1]]
## [1] 1 4
## 
## [[2]]
## [1] 2 3
## 
## [[3]]
## [1] 3 2
## 
## [[4]]
## [1] 4 1