GATE CSE
First time here? Checkout the FAQ!
x
0 votes
91 views

Consider the array of size n. the first (n – 1) elements are already sorted. What is the worst case time complexity to insert a nth 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(n2)
asked in Algorithms by Veteran (11.1k points)   | 91 views
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??

1 Answer

+2 votes
Best answer
it's take O(n)

because in worst case , we need to shift (n-1) elements
answered by Active (1.2k points)  
selected by
Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users