promotion image of download ymail app
Promoted
Anonymous
Anonymous asked in Computers & InternetProgramming & Design · 1 year ago

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

1 Answer

Relevance
  • 1 year ago
    Favourite 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

    • Hanna1 year agoReport

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

    • Commenter avatarLog in to reply to the answers
Still have questions? Get answers by asking now.