The Gateway to Computer Science Excellence
+1 vote

In Randomized Quick sort, Can we have partitioning algorithm that never gives worst case as $O(n^2)$  for every input?

in Algorithms by Active (3.6k points)
retagged by | 114 views

1 Answer

0 votes

 Randomized Quick sort worst case is o(n^2).

suppose we take a pivot element and it is divided(partitioning) the array in two sub array . like one array have 0 element and other array have n-1 element then recurrence relation become

  • T(n)=T(n-1)+o(n).
  • time complexity=o(n^2)
by Boss (35.6k points)
edited by
What about partition algorithim?
Partition will always take o(n) in worst case.

Related questions

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
50,648 questions
56,430 answers
99,923 users