How does 20 * 2 billion take as long as 2 * 3 in Big O Notation?

user_15055208 0
Viewed 60

Im studying big O and I came across this

function timesTwo(num) {
  return 2 * num
}
let result = timesTwo(5) // 10
let result2 = timesTwo(2000) // 4000

then it says this

Now, which of these do you think will take the longest to compute? 2 * 5 or 2 * 2000?...It’s just one operation (one multiplication). 20 * 2 billion takes as long as 2 * 3. No matter the size of the input, the function takes the same amount of time to compute.

How is that true?? how does that work? it seems to me that 20 * 2 billion would take significantly longer the 2 * 3

To make matters more unclear, it goes on to say this.

function manyTimes(num) {
  let total = 4 * num
  return total * 3
}

Now, we wouldn’t say this function has a Big O of 2, it’d still just be a Big O of 1 because we’re looking at the big picture (1 operation isn’t gonna take significantly longer than 2 for a computer so we can just ignore it). No matter what we put in, the number of operations won’t increase in the function, it’s constant time.

can you please explain the bolded text above.. ok 1 operation isnt significantly longer than 2. But what about 1 compared to 20,000 operations?

Source where I read this information. Big O Notation In Javascript

big-o javascript
2 Answers

Big O doesn't refer to exactly how long it takes for something to process, but rather how the length of the process grows with N inputs. Linear functions grow more slowly than exponential functions, meaning that Linear is faster to process in Big O.

Your example here compares two linear expressions, meaning that the growth for both is the same. I would say that it is inaccurate to say that they take the same time however, but rather that they grow at the same rate.

user_116833940

it's about tail behavior with input n stretching upwards to infinity. we are only concerned about how the tail of computational complexity trends at the end stages of that tail, because we would generally want to build algorithms in mind for the worst case scenario. 20x2billion is still O(n) just as 2x3 is still 0(n)

user_158123280
Related