I thought "NlogN" is "N" times "logN", but why is it described as "double PLUS an amount proportional to N"

user_5581182 0
Viewed 1486

I'm currently learning about the big O notation. In the material, O(NlogN) was described as Doubled plus an amount proportional to N. But I thought that would be O(N + logN) and not O(NlogN) (I thought O(NlogN) is Double times logN).

Is there something logically wrong with my understanding?

enter image description here

collections algorithm
1 Answers

Replace N with 2N as stated:

2N log 2N = 2N * (log N + log 2) (using logarithm rules)

  • Doubled original term 2 * (N log N)

  • Additional term (2 log 2) * N i.e. "proportional to N".

user_102653650
Related