GATE CSE
First time here? Checkout the FAQ!
x
0 votes
128 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 (13.2k points)   | 128 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.3k points)  
selected by


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users