Question

Consider the array of size n. the first (n – 1) elements are already sorted. What is the worst case time complexity to insert a n^th element in an array after insertion the array should be in sorted order

1.   O(1)
2.   O(n)
3.   O(n log n)
4.   O(n²)

Comments

i think this is same as last iteration of insertion sort

to insert nth element into already sorted array of size (n-1),we have to compare maximum with (n-1) elements and shift (n-1) in worst case..so T(n) should be O(n)

am i correct??

Answer 1

it's take O(n)

because in worst case , we need to shift (n-1) elements

Answer 2

It will be taking O(n) time