CODEWITHSUNDEEP
algorithmsortingcomparison
IUnknown
IUnknown

Reputation: 9809

Comparison of 'comparison' sorts

I read the following statement while comparing heap sort and merge sort:

Merge sort can be adapted to operate on linked lists with O(1) extra space. Heap sort can be adapted to operate on doubly linked lists with only O(1) extra space overhead.

Would appreciate help in explaining this (am not computer science educated) — though I understand the how the above sorts work at an elementary level.

Upvotes: 0

Views: 108

Answers (1)

stan0
stan0

Reputation: 11807

This is a Big O Notation. It is used to describe the complexity (time/memory usage) of an algorithm (check the link for more details). What is meant here is that the algorithms you read about can be extended to work in the mentioned cases and the change needed to be made would result in a constant-more space required. That is the extra space would not depend on the size of the structure. It would be constant - for example one variable more.

EDIT:

Some of the most used notations:

  • O(1) - constant - the time or memory used does not depend on the size of the structure the algorithm works on
  • O(n) - linear - depends on the size of the structure - the bigger the structure - the more time/memory is required
  • O(logn) - logarithmic ...

For more details check here

Upvotes: 3

Related Questions