Ch.10
Lower Bound Theory

From the text:

f (n) - running time of some algorithm

g (n) - lower bound -- (Omega)


iff there exists positive constants c and no such that f(n) > cg(n) for all n , n > no (g(n) is a lower bound for f(n))

if f(n) > O(g(n)) and
then asymptotically, we cannot have any improvement.
Improvement in constant possible.

Trivial lower bounds:

Max of set of n numbers
have to look at all inputs, n-1 comparisons : f(n) is O(n) ; (n)

n x n matrix multiplicaton: 2n2 inputs , n2 outputs
(n2)

but this is lower than the best known algorithm

Best known algorithm requires f (n) = 0 (n2 + )

Improvement possible or tighter lower bound exists. (See Chapter 3 for more details.)

Comparison Trees: Searching/Sorting

Useful for modeling the way in which a large number of sorting and searching algorithms work,

Comparison-based algorithms - algorithms which work solely by making comparisons between elements; no arithmetic involving elements is permitted

A [1 : n]

p: permutation of {1, 2, . . . ., n}

The sorting problem calls for determining p, a permuation of the integers 1 to n, such that the n distinct values from S (the Set) stored in A[1:n] satisfy

A (p (1)) < A (p (2)) < . . .< A (p (n)) (ordering in terms of indices, not values) p(1) is the first in the permutation.

The ordered searching problem : A (1) < A (2) . . .< A (n)

again: restriction on class of algorithms for which lower bound applies -
only comparison between elements - no arithmetic on keys.

Comparison Trees

Search

Linear Search (ordered array)

running time - longest path in tree
- O(n)

Binary Search

In general

f (n) = O(log n)

If search terminates at interior nodes - success . . . . . external (leaf) nodes - failure

How do we reason to determine lower bound?

So best - optimal algorithm is binary search since it achieves this

Note that we did not look at any specific algorithm to detemine the lower bound, instead we considered information about the problem and considered what is the best we could do.

And, actually, we would want to consider the worst case of our best algorithm. Why? To see if it is the best possible.

Sort

comparison tree for sorting

number of external (leaf) nodes = number of distinct permutations of {1, 2, . . ., n}

= n!

let k be max. level of any internal node in tree

T(n) = k

If max level of any internal node is k, then at most 2k external nodes
n! < 2k      ;      k = T(n) > log2(n!)

By Stirling's approximation (see page 462) = O(n log n)
Hence any comparison-based sorting algorithm needs (nlog n) time

Selection

see text

Oracles

From the text

Polynomial Reductions

Here we discuss a very important technique that can be used to derive lower bounds. This technique calls for reducing the given problem to another problem for which the lower bound is already known.

Two problems L1 and L2

T1 (n) = time to solve L1

T2 (n) = time to solve L2

L1 L2      L1 reduces to L2     implies T1(n)    <   p(n) * T2(n)     Where p is some polynomial

Definition: Let P1 and P2 be any two problems. We say P1 reduces to P2 in time p(n) if an instance of P1 can be converted into an instance of P2 and a solution of P1 can be obtained from a solution of P2 in time <   p(n) 

 
proc L1 (	)		proc L2 (	)
   call L2 (	)

end				end
For each instance l1 of L1 construct an instance l2 of L2 such that a solution to l1 can be recovered from a solution to l2.

(size n2 since we may need to add some more structure to our problem in order to cast is as a problem in L2)

T1 (n1)     =     t12 + T2(n2) + t21    <    p(n1) * T2 (n1)
n2 = poly (n1) (i.e., must be bounded by a polynomial in n1 - otherwise, t12 non polynomial) what?

T1 (n1)     <    p(n1) * T2 (n1)

L1: single source shortest path in undirected graphs

L2: single source shortest path in directed graphs 

proc	L1 (G = (V,E), c(E), p)
	// G - undirected graph
	// c  - edge costs
	// p - shortest path 

	// construction: instance of  l1 making it an instance of l2 
        //   make all directions go both ways

E->= { (u,v)->, (v,u)-> | (u,v)  E}


G-> = (V,E->)


c(u,v)-> = c(v,u)-> = c(u,v) for all (u,v)  E 

call L2 (G->=(V,E->), c(E->), p)

// recover //

p =	undirected version of p->

end
(Notice that part that says undirected version of p->)
This is important...any directed to undirected does not work - it needs to maintain the information (we will see this in next lesson)

Claim:      p shortest path in G       <==>       p-> shortest path in G->

not for any directed graph ... for ones considering in such a problem reduction

Proof:

In human words...why does this work?

Cost of construction + recover = O(|V| + |E|)

T1 (n1) < poly (n1) * T2 (n2)       number of edges in directed is at most twice what it was before

If T2(n) is also polynomial in n then we go one step further
T1(n1) <     t12 + T2(n2) + t21    <   t12 + t21 + poly(n) * T2(n1)   < poly2 (n1) * T2(n1)

and T1(n1) is hence some poly. in n.