First time here? Checkout the FAQ!
0 votes

asked in Algorithms by (275 points) 1 5 18 | 40 views

1 Answer

+2 votes

Choose the median in constant time, because the algorithm is implemented as an array and you can find the median in constant time.

Then, split the array with respect to the median.

The recurrence relation will be:

T(n) = 2T($\frac{n}{2}$) + 1

(1 because we are doing a constant work and then splitting the array)

Solve by master's theorem, you will get $\Theta (n)$

NOTE: If the data structure used was a linked list or if the elements were not in ascending order, the complexity would have been $\Theta (nlogn)$

answered by Veteran (10.2k points) 6 44 108
edited by

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23684 Points

  2. Bikram

    17288 Points

  3. Habibkhan

    9194 Points

  4. srestha

    6486 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5168 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4504 Points

  9. sushmita

    4080 Points

  10. Rishi yadav

    3998 Points

Recent Badges

Nice Comment Pooja Palod
Famous Question Harsh181996
Verified Human ASK
Good Comment Bikram
Good Comment Arjun
Nice Comment Arjun
Famous Question Meenakshi Sharma
Famous Question Meenakshi Sharma
Nice Question smartmeet
Nice Comment Vicky rix
27,426 questions
35,275 answers
33,523 users