A&DS S01E03. Quick sort. Order statistics

Algorithms and data structures. Semester 1. Lecture 3.

In the third lecture, we learned the quicksort algorithm, discussed how to estimate the running time of randomized algorithms, and also considered a related problem: finding the K-th order statistic.

ITMO University, 2020

[chukad]

Content of this lecture:
1.Randomize algorithm intro
2.Quick Sort with randomizer
3.Time complexity analysis of above
4.Order Statistics with randomizer
algorithm for selecting a good pivot point

[abcd-sfur]

you are great sir! thanks for providing this high quality content

[piyushnaithani]

Parvel, it would be great if you post your screencast during contests like Hackercup, CF div1.

[dineshkumar-kgir]

Pavel can you problem discussion video as well?

[madhukiranattivilli]

If T(n)=10n for algorithm algo to get k-th element in a sorted list but T(n)=3n using randomized algo

Can we say that the randomized technique is actually FASTER than the deterministic technique?

[PatrickHwangg]

I've just finished my 10-grade school year. I don't quiet understand those mathematical letters. Can anybody please describe it for me? Thanks.

[afzalghani]

You will not find this kind of content anywhere on youtube.

[madhukiranattivilli]

58:00 -- I got the sum of n + 2n/3 + 4n/9 + ... = 3n not 3n
Slight difference -- doesn't matter -- it is O(n) -- but I didn't get exactly 3n :)

T(n) = n + 2n/3 + 4n/9 + 8n/18 + ... + ((2/3)ˆk)*n
let t = 3/2
T(n) = n/t⁰ + n/t¹ + n/t² + ... + n/tˆk
T(n) = n/tˆk * (tˆk + tˆk-1 + tˆk-2 +... + t² + t¹ + t⁰)

Let array size become 1 after k recursive calls
n/tˆk = 1
k = log<t>n

T(n) = 1 * (t⁰ + t¹ + t² + ... + tˆk)
Let t⁰ + t¹ + t² + ... + tˆk = z
z = 1 + t * (t⁰ + t¹ + t² + ... + tˆk-1 + tˆk - tˆk)
z = 1 + t * (z - tˆk)
z = 1 + tz - tˆk+1
z(t-1) = tˆk+1 -1
z = T(n) = tˆk+1 -1 / t-1

n = tˆk
n*t = tˆk+1

nt - 1 = 3n/2 - 1 = 3n-2 /2
t - 1 = 3/2 -1 = 1/2
T(n) = 3n-2 = O(n)

[shahbazalam]

Can you please upload videos for this lecture series a little bit sooner. I think the gap of a week is going to be too much.