Algorithmic Efficiency Practice Test

A smartwatch app computes Fibonacci numbers for animations; it may request n up to 45, and each computation must finish under 0.1 seconds. Two approaches are given:

Pseudocode (Naive Recursion):

FIB_RECURSIVE(n)

  IF n <= 1

    RETURN n

  RETURN FIB_RECURSIVE(n-1) + FIB_RECURSIVE(n-2)

Time complexity: $O(2^n)$

Pseudocode (Dynamic Programming):

FIB_DP(n)

  IF n <= 1

    RETURN n

  prev <- 0

  curr <- 1

  FOR i <- 2 TO n

    next <- prev + curr

    prev <- curr

    curr <- next

  RETURN curr

Time complexity: $O(n)$

Considering the time complexities mentioned, which algorithm has a lower time complexity for large inputs?

A data team must sort sensorReadings each minute. Input size can spike from 1,000 to 100,000 readings, and each minute’s sort must finish before the next batch arrives. Two algorithms are compared:

Pseudocode (Bubble Sort):

procedure bubbleSort(sensorReadings)

  n <- length(sensorReadings)

  for i <- 1 to n - 1

    for j <- 1 to n - i

      if sensorReadings<u>j</u> > sensorReadings<u>j + 1</u>

        swap(sensorReadings<u>j</u>, sensorReadings<u>j + 1</u>)

Time complexity: $O(n^2)$.

Pseudocode (Merge Sort):

procedure mergeSort(sensorReadings)

  if length(sensorReadings) <= 1

    return sensorReadings

  mid <- length(sensorReadings) / 2

  left <- mergeSort(sensorReadings<u>1..mid</u>)

  right <- mergeSort(sensorReadings<u>mid+1..end</u>)

  return merge(left, right)

Time complexity: $O(n \log n)$.

Considering the time complexities mentioned, which algorithm has a lower time complexity for large inputs?