Search code examples
time-complexity

find amortized time complexity in insert m items into a sorted array

I have an sorted array with length of n and want to insert m new Item so that after each insertion array should be sorted. Suppose Accidentally(We do not know in advance) in each insertion item Insert in the middle of the array.

How is the number of operations required for m insertion calculated?

and amortized time complexity ?

Solution

  • You'll shift half the elements for each insertion, so:

    n/2 + (n+1)/2 + ... + (n+m-1)/2
    = (n/2 + (n+m-1)/2) * m / 2
    = O((n+m)m)
    = O(mn + m²)

    Amortized is no different here.