educative.io

Feedback on runtime analysis

Courses
,
#1

Hello,

Just wanted some feedback on runtime analysis. I’m still learning. My question is whether the solution I came up with below runs in O(N^4) or O(N^3). Or something else entirely. Thanks in advance.

const find_subarrays = function(arr, target) {
  let result = [];
  let intermediaryArray = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < target) { 
      result.push(arr[i]);
    }
    intermediaryArray = [];
    intermediaryArray.push(arr[i]);
    for (let j = i + 1; j < arr.length; j++) { 
      intermediaryArray.push(arr[j]);
      const product = intermediaryArray.reduce((acc, curr) => acc * curr);
      if (product < target) { 
        result.push(intermediaryArray.slice());
      }
    }
  }
  
  return result;
};
#2

Above code Shows time complexity of O(N^2)

Reason below:
1st For loop O(N)

for (let i = 0; i < arr.length; i++) {

2nd for loop is indie first for loop , hence O(N)*O(N)==> O(N^2)

for (let j = i + 1; j < arr.length; j++) {

you can check this youtube link.

#3

This is actually not 100% correct. The algorithm is O(N^3) because of the two loops plus the added intermediaryArray.reduce() call (as well as the .slice call).

Technically is more like O(N^2 * (2N)) But the amortized runtime is O(N^3)