-1

I am confuse about the big O notation.

O(n^2) -> it grows quadratically, when you double the size of n, the number of operations would actually be multiplied by a factor of 4.

O(n*log(n)) -> when you double the size of n, the number of operations would actually be multiplied by a factor of how much???

2n*log (2n)  / n*log(n) = 2*log(2n)/log(n) =2*log_n (2n)

Is this the factor?

Nygen Patricia
  • 229
  • 2
  • 8
  • 1
    Yup, it depends on the value of `N`. For large values it's going to approach 2 (but always be larger than that). – mszymborski Aug 15 '16 at 23:22
  • 1
    Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) –  Aug 15 '16 at 23:29
  • http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation?rq=1 http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds?rq=1 http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly?rq=1 etc –  Aug 15 '16 at 23:29

1 Answers1

1

The O (big-oh) notation is the boundary in the asymptotic case, it's related to the number of operations although not an exact figure.

If you double n in a O(n log n) processing algorithm you have.

log (2n) = log(n) + log(2) so you could assume you would have

2 (log(n)+log(2) / log(n)) times the initial operation.

Or as @Jeremy said 2(1+log base n of 2)

ppaulojr
  • 3,579
  • 4
  • 29
  • 56