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.

- Worst case in Max-Heapify - How do you get 2n/3?
- Why when I use .size() to compute the length of array in the Conditional Determination of for Loop Structures will time out in leetcode?
- What is the formal definition of Θ(f(n)) without expressing Θ(f(n)) in terms of O(f(n)) or Ω(f(n))?
- Sorting an array with a repeating element (given its frequency) in linear time
- What is the Big-O of this function that reverses words in a string
- Why is the time complexity of Python's list.append() method O(1)?
- How can I apply meet-in-the-middle algorithm for searching whole 2D matrix
- lru_cache vs dynamic programming, stackoverflow with one but not with the other?
- c++ bitset logical operations in O(log n)?
- Time complexity of while loop inside for loop
- Time complexity of simultaneous iteration
- Time complexity for recursive binary search that also prints current subarray
- What's the Time Complexity of two separate inner loops nested in an outer loop?
- how to calculate binary search complexity
- Time complexity of StringBuilder reverse method
- How should I calculate the Time complexity for the below code?
- Big O notation of string permutation in Python
- Count number of digits - which method is most efficient?
- most efficient way to compute f(n)^f(n) where f(n)=n^n and n has 15-20 digits
- Big O of algorithm that steps over array recursively
- Why is O(n) better than O( nlog(n) )?
- How can the time complexity for this algo be O(N)?
- Find max product using divide and conqure in O(n) time
- Rough estimate of running time from Big O
- Calculation of time complexity of a function that finds all possible sum combinations of a given number from the list
- Find occurrences of subsequence in a binary string (non-necessarily-contiguous)
- Is complexity O(log(n)) equivalent to O(sqrt(n))?
- Leetcode 2161: Partition array according to given pivot
- Time Complexity of my program in competitive programming question City Plan
- How to calculate the time complexity of this recursive function