CODEWITHSUNDEEP
big-o
Laurence Wingo
Laurence Wingo

Reputation: 3952

What does it mean to drop the constants in terms of big o notation?

I'm watching a video on Hackerrank in regards to Big O Notation and while reading materials from the Career Cup, I always hear the term 'drop the constants'. Please let me know if I'm understanding correctly based on the algorithm below:

    function whyWouldIDoThis(array){
     max = NULL
    for each a in array {
      max = MAX(a, max)
    }
    print max
    for each a in array {
      for each b in array {
        print a,b
      }
    }
   }

It was explained that since these are two separate for loops, then the first for loops is O(n) and the second for loop is O(n^2) and since its all one algorithm then it ultimately becomes O(n^2). It makes sense that since the term 'n' is the same then they cancel out. Is this the meaning of 'dropping the contents' in terms of Big O Notation?

Upvotes: 2

Views: 984

Answers (1)

fractals
fractals

Reputation: 856

max = NULL ----------------- c_1
for each a in array {
  max = MAX(a, max) -------- c_2
}
print max ------------------ c_3
for each a in array {
  for each b in array {
    print a, b ------------- c_4
  }
}

Analyzing the code line-by-line, we have that the total time taken would be

c_1 + c_2 * n + c_3 + c_4 * n * n = c_4 n^2 + c_2 * n + c_1 + c_3

Now we only need the dominant term, which is c_4 n^2, and the coefficient c_4 is not needed either. So we have O(n^2).

In this sense, "dropping the constant" is to drop the coefficient. That is, even if your code might be slightly faster than O(n^2), maybe O(n^2 / 2), it does not matter in terms of Big-Oh; it's all O(n^2).

Upvotes: 3

Related Questions