2

I have just started "Cracking the Coding Interview" by Gayle Macdowell. In this BigO topic, It says we should drop the non-dominant term.

O(n^2 + n) becomes O(n^2) and O(n + log n) becomes O(n).

Well, I understand that. If we suppose the value of n to be some large number then we can ignore the smaller result since, it will be comparatively much more smaller than the larger one.

But, in this case how can O(5*2^n + 1000n^100) become O(2^n)) ?

Isn't n^100 dominant than 2 ^n ?

JJ123
  • 573
  • 1
  • 4
  • 18
  • 1
    big-O is about how something scales over time; whether there's a big constant or small constant doesn't matter, since the other part of the scale increases exponentially in this case. – Joe Jun 02 '17 at 00:49
  • Nitpick: It's not `BigO(n)`, it's just `O(n)`. – Bernhard Barker Jun 02 '17 at 08:36

1 Answers1

2

n^100, or n raised to any constant, does not dominate 2^n.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • 1
    if n = 100, isn't ( 100 ^ 100 > 2 ^ 100 ) ? or, do you mean that the constant(i.e 100) in n ^ 100 is dropped ? – JJ123 Jun 02 '17 at 01:00
  • 2
    For a sample size of n = 100, an algorithm that requires 2^n operations will be faster than an algorithm that requires n^100. But Big-O notation is not about the number of operations for any fixed size - it is a way of describing the way the algorithm scales as n becomes arbitrarily large (i.e. approaches infinity). – BJ Myers Jun 02 '17 at 01:08
  • It seems little easier now. Thanks! – JJ123 Jun 02 '17 at 01:23