A simple expected running time analysis for randomized “divide and conquer” algorithms

There are many randomized “divide and conquer” algorithms, such as randomized Quicksort, whose operation involves partitioning a problem of size n uniformly at random into two subproblems of size k and n - k that are solved recursively. We present a simple combinatorial method for analyzing the expe...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2006, Vol.154 (1), p.1-5
Main Author: Dean, Brian C.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Classical combinatorial problems
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Divide and conquer
Exact sciences and technology
Mathematics
Probabilistic recurrence
Quicksort
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There are many randomized “divide and conquer” algorithms, such as randomized Quicksort, whose operation involves partitioning a problem of size n uniformly at random into two subproblems of size k and n - k that are solved recursively. We present a simple combinatorial method for analyzing the expected running time of such algorithms, and prove that under very weak assumptions this expected running time will be asymptotically equivalent to the running time obtained when problems are always split evenly into two subproblems of size n / 2 .
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2005.07.005