Anonymous
Anonymous asked in Computers & InternetProgramming & Design · 7 months ago

Explain why, in the worst case, the number of comparisons is of O(n^2) for the insertion sort.?

1 Answer

Relevance
  • 7 months ago
    Favorite Answer

    When a new item it inserted it has to be compared to all the other items present.

    At first there's 1

    then 2

    then 3

    ...

    then n

    Add all these up and it's n(n-1)/2 which neglecting the 1 and the factor ½ equals n^2

    • Hanna7 months agoReport

      thank you sooooo muuchhh Quentin for answering my question i appreciate it :)

Still have questions? Get your answers by asking now.