CODEWITHSUNDEEP
algorithmsortingmathtime-complexitybig-o
Sanjay Verma
Sanjay Verma

Reputation: 101

Time complexity of the merge sort

enter image description here

My Doubt is that I don't understand which property or how they take common in line no. 3

Can someone please explain in simple language?

Upvotes: 0

Views: 97

Answers (3)

Emma
Emma

Reputation: 27723

I guess maybe it would be simpler than that:

  • n numbers can be sorted in n log n of time.
  • The question is how many numbers can be sorted in n of time.

It would be then as simple as:

enter image description here

Upvotes: 1

shiponcs
shiponcs

Reputation: 1677

It's not about taking common, in "[longn - loglogn = O(logn)]" they actually explained the logic, this portion is separate from the original expression.

I think they tried to write in this way, "[O(logn - loglogn) = O(logn)]"

Upvotes: 1

Guang Yang
Guang Yang

Reputation: 11

It's just by definition of the big-O notation: O(log n - loglog n)=O(log n) (In fact it should be big-Theta here).

Upvotes: 1

Related Questions