Time Complexity · #68

What's the Big-O?

JavaScript ·Difficulty 2/3

How to play

Read the code and pick its time complexity from four Big-O choices. Think about loops, recursion, and hidden costs. Press 1–4 or click to answer.

m = a.length, n = b.length. What is the time complexity?

function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0)
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[a.length][b.length];
}

Loading your progress...

Press 1 through 4, or tap a numbered choice, to answer. Back to hub