-1

I have been learning about sorting algorithms and understand the idea of time and space complexity. I was wondering if there was a fairly quick and easy way of working out the complexities given the algorithm (one that may even be quick enough to do in an exam) as opposed to learning all of the complexities for the algorithms.

If this isn't an option, is there an easy way to remember or learn them for some of the more basic sortings algorithms such as merge sort and quicksort.

6C69616D
  • 72
  • 10
  • 1
    You have to read the proofs and then you will develop an intuition for remembering them. Of course there is no simple way to tell what complexity of a given algorithm is but you can guess that if there is divide and conquer going on, there will be a logn somewhere. – MK. Aug 22 '19 at 14:52
  • 1
    Merge sort is *O(n log n)*, and QuickSort *O(n^2)*. Repeat that every day, and I think eventually you remember that. It is however usually better to understand *why* that is the case, by looking at some proofs, etc. you eventually can frequently correctly "guess" the timecomplexity, and develop shortcuts to proof it. – Willem Van Onsem Aug 22 '19 at 14:58

1 Answers1

1

You have to memorize this:

enter image description here

It depends on the problem. Best option in different situations:

  • In place and stable: Selection Sort
  • In place (don't care about stable): Heap Sort
  • Stable (don't care about in place): Merge Sort
Hadi GhahremanNezhad
  • 2,377
  • 5
  • 29
  • 58