Best : $\Omega \left ( nlogn \right )$ worst = O(n^{2})

The Gateway to Computer Science Excellence

+1 vote

You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the **best case **performance is

a) O(n2)

b) O(nlogn)

c) Θ(nlogn)

d) O(n3)

0

It is normal quick sort in which we are selecting the middle element as the pivot so the best case will be that it is divided into two equal parts giving the time complexity of O(nlogn).

In the worst case the it will take O(n^2) as the middle element selected can divide the array into two parts of 0 element at one side and n-1 at other.

now in the question it is asking for the lower bound in the best case.

the time complexity in best case is O(nlogn)

now tightest lower bound means the least possible time in which the problem can be solved.

in this case tightest lower bound is O(nlogn).

In the worst case the it will take O(n^2) as the middle element selected can divide the array into two parts of 0 element at one side and n-1 at other.

now in the question it is asking for the lower bound in the best case.

the time complexity in best case is O(nlogn)

now tightest lower bound means the least possible time in which the problem can be solved.

in this case tightest lower bound is O(nlogn).

+2 votes

Best answer

** best case= o(nlogn)**

**If we choose central element as pivot then array is divided into two equal part. And recurrence relation become T(n)=2T(n/2)+n which will take o(nlogn) time. **

**Worst case =o(n^2).**

**If we choose central element as pivot then array is divided into two part one part contain 0 element and other part is n-1 element. And recurrence relation become T(n)=T(n-1)+1 which will take o(n^2).**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,429 answers

195,205 comments

99,907 users