Lower Bound Analysis

• We can analyze the behavior of a particular algorithm on an arbitrary list by using a tree.

i,j

k,l

m,n

q,p

t,s

r,w

x,y

L[i]<L[j]

L[i]>L[j]

L[k]<L[l]

L[k]>L[l]

L[m]<L[n]

L[m]>L[n]

Previous slide

Next slide

Back to first slide

View graphic version