Search code examples
algorithmanalysisinsertion-sort

cost of lines in algorithm help me understand this

https://i.sstatic.net/vBCeD.png

https://i.sstatic.net/aodkF.png

Okay so basically i have an algorithm of an insertion sort, however next to it is a constant which is the cost of running each line of code

now my mathematical background is not very strong but i do understand most of it, however what i cannot make sense of is why is the coefficient of n^2 and n have the constants divided by two?

what is the significance of it? is it because it is a loop within a loop? or maybe because two values are compared? or some other mathematical reason like formula of summation n(n-1)/2

first image is the algorithm in pseudo code and the summation under it the best case scenario(where the algorithm is already sorted) and the second picture is the algorithm worst case scenario(summation) which is where my question is pointed at

note: also tj denote the number of times the while loop test in line 5 is executed for that value of j

Solution

  • Its a boring night and I wanted to play with latex, so to expand on the comment i left into an actual answer...

    To summarize your question.

    Lets start with a basic example.

    Which is equivalent to

    This is where the form comes from. Back to a parameterized sum, we can now see that.

    Note the variable i starting at 1. The sum for the algorithm calls for the variable to start at 2. Logically, the sum will be 1 less, so

    To carry it out further... (for one term)