# Probabilistic Analysis of the Randomized QuickSort Algorithm

This article will cover the probabilistic analysis of the randomized Quicksort algorithm. The randomness comes from selecting the pivot to partition the input array around uniformly.

# Overview / Pseudocode

Quicksort is an efficient algorithm that solves the sorting problem; that is, given an input array A and its length n, find a permutation of A such that for all i, j (0 ≤ i < j < n), A[i] < A[j]. The running time of Quicksort is in the order of Θ(n log n). …

# Lower Bound for Comparison Based Sorting Algorithms

## Introduction

Sorting is an essential problem that shows up in many areas of computer science. To state precisely, the sorting problem takes an input array A with n distinct elements and outputs a permutation of A such that for all i and j (i < j), A’[i] < A’[j]:

Sorting algorithms (algorithms that solve the sorting problem) generally use comparison to sort an array, that is, the algorithm makes a comparison between some (or all) pairs of distinct elements in the array. …

# Creating your own HTTP Server — Part I 