Design and Analysis of Algorithms
Lecture 2
Partha Sarathi Mandal
Dept. of Mathematics, IIT Guwahati
Design and Analysis of Algorithms
• We will see how to design and analyze
algorithms that:
– Produce correct results
– Are efficient in running times and space usage
• Purpose of design should be obvious:
– One needs an algorithm in order to write a
program!
P. S. Mandal, IITG
Why do we need to analyze algorithms?
• Theoretical analysis more reliable than
experimentation (guarantee performance on all inputs)
• Choose among different solutions (without requiring
that all solutions be implemented and tested)
• Predict software performance before writing code (in
large projects do analysis first to discover speed
problems and work around them)
• Gain better understanding of where fast and slow parts
are (what to work on or work around to speed it up)
Example: the 1GB sorting problem
P. S. Mandal, IITG
• Algorithmic efficiency can make the difference
P. S. Mandal, IITG
THE 1GB SORTING PROBLEM
P. S. Mandal, IITG
THE 1GB SORTING PROBLEM
P. S. Mandal, IITG
Do you think it is better
a fast algorithm
or a fast computer?
• A problem on this in the first homework
P. S. Mandal, IITG
Questions so far?
P. S. Mandal, IITG
Recap
• Heapsort: Asymptotically optimal but needs to
move data around. Can be implemented so that
uses little extra memory. Probably good when
memory is tight and data stored in array
• Mergesort: Uses even fewer comparisons than
heapsort. Especially suited for data stored as
linked lists. Good for data too big to fit in memory
(regular pattern of storage access)
• Quicksort: Not optimal but uses few comparisons
in practice (less than other two). Like heapsort
can sort "in place" by moving data in array
P. S. Mandal, IITG
Can we do better than O(n log n) time?
• Not in general!
• The lower bound
P. S. Mandal, IITG
Lower bound
• Mathematical argument stating you can’t hope to go faster
than certain amount
• More precisely, every alg within certain model of
computation must have running time at least that amount
• Usually proved for worst case running times - could also do
for average case or best case
• Doesn’t necessarily mean faster algorithms are completely
impossible
• If want to go faster, can’t stick with abstract model, but
should look more carefully at problem
• We’ll see faster algs (won't contradict the lower bound!)
P. S. Mandal, IITG
Lower bound
• Amount of resource (time, memory) necessary
to solve certain problem
• Give some idea of how good alg you could
expect to find for that problem (know if there
is room for further optimization)
P. S. Mandal, IITG
Lower bound
• We’ll show that (n log n) is a lower bound to
the number of comparisons required to sort n
objects
• How?
• We need to show that any algorithm requires
(n log n) comparisons!
P. S. Mandal, IITG
Comparison Based Model
• In this model, algorithm can sort only by making
comparisons between objects
• Other operations, such as arithmetic ops (i.e.,
sums, products, etc.), logical ops (i.e., and, or,
etc.) or other ops (i.e., shifts, etc.) are not
allowed
• Sufficiently general to capture properties of
common sorting algorithms
P. S. Mandal, IITG
How to Prove Lower Bound
• Consider any sorting algorithm A, which sorts
by making only comparisons
• We have no idea about how A runs!
• Nevertheless, we will prove that A must take
at least (n log n) comparisons
• Since our only assumption on A is that A is a
comparison-based sorting alg, lower bound
will hold for all comparison-based algs!
P. S. Mandal, IITG
Decision Trees
• Formalism to represent comparison sorting algs
• Given comparison sorting alg A, and some
number n, decision tree illustrates behavior of A
on input of size n
P. S. Mandal, IITG
Decision Trees
• Tree corresponds to different sequences of
comparisons A might make on input of length n
• Each tree node represents positions involved at
some comparison
• Each tree path describes sequence of
comparisons and their results from particular run
of the algorithm.
• Each node has two children (result of the
comparison at that node)
P. S. Mandal, IITG
Decision Trees
= Comparison
Algorithms!
• Any comparison sorting alg can always be put in
the form of a decision tree:
– comparison it chooses at any time can only depend on
answers to previously asked comparisons!
• Conversely, decision tree can be used as sorting
alg:
– for any given input list, follow tree path to determine
which comparisons to make and which input
permutation gives sorted order
P. S. Mandal, IITG
Properties of Decision Trees
• On a given input, comparisons made by alg A
on that input is just a root-to-leaf path: at
each leaf no more comparisons to be made -
therefore we know what the sorted order is
• Worst case number of comparisons made by
alg A is just longest tree path (tree height)
• Each possible sorted order corresponds to a
permutation, so there are at least n! leaves
(might be more for stupid algs)
P. S. Mandal, IITG
How fast can we sort?
• All the sorting algorithms we have seen so far are
comparison sorts: only use comparisons to
determine the relative order of elements.
• E.g., insertion sort, merge sort, quicksort,
heapsort.
• The best worst-case running time that we’ve seen
for comparison sorting is O(n log n).
Is O(n log n) the best we can do ?
• Decision tree scan help us answer this question.
Decision-tree example
• Each internal node is labeled i:j for i, j ∈ {1, 2, …, n}.
• The left subtree shows subsequent comparisons if ai ≤ aj.
• The right subtree shows subsequent comparisons if ai ≥ aj.
Decision-tree example
• Each internal node is labeled i:j for i, j ∈ {1, 2, …, n}.
• The left subtree shows subsequent comparisons if ai ≤ aj.
• The right subtree shows subsequent comparisons if ai ≥ aj.
Decision-tree example
• Each internal node is labeled i:j for i, j ∈ {1, 2, …, n}.
• The left subtree shows subsequent comparisons if ai ≤ aj.
• The right subtree shows subsequent comparisons if ai ≥ aj.
Decision-tree example
• Each internal node is labeled i:j for i, j ∈ {1, 2, …, n}.
• The left subtree shows subsequent comparisons if ai ≤ aj.
• The right subtree shows subsequent comparisons if ai ≥ aj.
Decision-tree example
• Each leaf contains a permutation 〈π(1), π(2),…, π(n)〉
to indicate that the ordering aπ(1) ≤ aπ(2) ≤ … ≤ aπ(n) has
been established.
Decision-tree model
A decision tree can model the execution of any
comparison sort:
• One tree for each input size n.
• View the algorithm as splitting whenever it
compares two elements.
• The tree contains the comparisons along all
possible instruction traces.
• The running time of the algorithm = the length of
the path taken.
• Worst-case running time = height of tree.
Lower bound for decision-tree sorting
Theorem: Any decision tree that can sort n
elements must have height Ω(n log n).
Proof: The tree must contain ≥ n! leaves, since there
are n! possible permutations. A height-h binary
tree has ≤ 2h leaves. Thus, n! ≤ 2h.
∴ h ≥ log (n!) (log is mono. increasing)
≥ log ((n/e)n) (Stirling’s formula)
= nlog n – nlog e
= Ω(nlog n).
Lower bound for comparison sorting
Corollary: Heapsort and merge sort are
asymptotically optimal comparison sorting
algorithms.
