Question 271260 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – What would be the BIG O analysis in this case?

I am wondering what BIG O would be in this case? I thought it was O(1) since it has fixed number of iteration (the array.length is fixed)… and even if in the worst case (3999), still the max iteration is fixed… but also I saw the answer can be O(n), because it is a linear relationship with the value of num. For smaller values of num, the while loop will iterate fewer times, and for larger values, it will iterate more times, but the growth rate is linear.

I assume that even if the iteration is fixed, if it’s linear, the time complexity would be O(n)?

function convertRomanNumerals(num) {

  let romanNumerals = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [5, "V"],
    [4, "IV"],
    [1, "I"]
  ];

  // 1 =<num =d<3999
  // 1990 = M CM XC
  // 1666 = M DC LX VI
  let result = "";

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

    while (num >= romanNumerals[i][0]) {
      result += romanNumerals[i][1];
      num -= romanNumerals[i][0];
    }

  }
  return result;

}
console.log(convertRomanNumerals(2023))
Tags:

2

Answers


  1. 0

    We can count the number of iterations and get some statistics out of it

    function convertRomanNumerals(num) {
  let iterations = 0

  let romanNumerals = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [5, "V"],
    [4, "IV"],
    [1, "I"]
  ];

  // 1 =<num =d<3999
  // 1990 = M CM XC
  // 1666 = M DC LX VI
  let result = "";

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

    while (num >= romanNumerals[i][0]) {
      result += romanNumerals[i][1];
      num -= romanNumerals[i][0];
      iterations += 1
    }

  }
  return iterations;

}

const data = []

for (let i = 1; i < 400000; i += 1) {
  data.push(convertRomanNumerals(i))
}
console.log(data[0], data[5000], data[20000], data[35000])
const avg1 = data.slice(0, -1).map((a, i) => data[i + 1] - a).reduce((a, b) => a + b) / (data.length - 1)
const avg2 = data.slice(0, -1).map((a, i) => data[i + 1] / a).reduce((a, b) => a + b) / (data.length - 1)
console.log(avg1, avg2)

    It increases but very slowly so it’s not O(1) for sure

    Login or Signup to reply.
  2. 0

    In order to properly understand complexity, we need to properly understand the concept of infinity.

    First, there is the concept of actual infinity, which is either infinitely large or infinitely small.

    Second, there is the concept of cluster point, that is, a threshold beyond which we do not care about the actual bounds, given the fact that it is too large or too small.

    For example, if you have to walk 30 000 miles, then it is not actual infinity, but it is beyond the treshold where you still care about the size.

    So, when people analyze functions, then they either arbitrarily or with good reason choose an error limit, that is, the maximum distance between the value you are approaching and the actual value, that is, the maximum error you allow. This specifies where your cluster point is.

    Now, complexity is the function which determines the pattern which your algorithm follows as, with the increase of the input size, its number of steps approaches infinity.

    Your situation is that your input size is guaranteed to always be small, so you will never reach the cluster point when it becomes too slow. But your function’s complexity is not determined on how it performs when the size of the input is next to nothing, but it is determined in terms of how quickly it reaches the cluster point where you no longer wait for it to be executed.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search