The resource can be the time and the space. We will concentrate mostly on time in this course. However, sometimes 'time' and 'space' can be trade-off.
n -- linear
n^2 -- quadratic
n^3 -- cubic
n^k -- polynomial
c^n -- exponential
The problem is said to be 'easy' if it is in the group of 'polynomial' and is 'hard' if it is in the group of 'exponential'.
asymtotic "in the order of t(n)"
best worst
Insertion n
n^2
Selection n^2 n^2
to analyse average case, the distribution of instances of size n must be known.
We call the running time of each operation -- unit cost
find determinant
-- recursive def
n!
-- Gauss-Jordan
n^3
-- Strassen (1971) divide-conquer n^lg7 = n^2.81
sorting
average worst
-- quicksort
n log n n^2
-- heapsort (Williams 1964) n log n
n log n
-- mergesort
n log n
n log n
-- pigeonhole sort
n
n
-- multiplication m, n
mn
-- mul divide-conquer
n m^log(3/2)
if n = m, n^1.59
-- mul best (ref?)
n log n log log n
show multiplication normal and divide and conquer
shift
09 12 4 108....
09 34 2 306..
81 12 2 972..
81 34 0 2754
-------
1210554
each two digits can be furthur divided into one digit mul.
(09 * 12)
0 1 2 0..
0 2 1 0.
9 1 1 9.
9 2 0 18
---
108
cost times
insertion-sort(A)
for j=2 to length(A) c1
n
key = A[j]
c2 n-1
i = j - 1
c4 n-1
while i>0 and A[i]>key c5 sum j=2
to n (t_j)
A[i+1] = A[i]
c6 sum j=2 to n (t_j - 1)
i = i - 1
c7 sum j=2 to n (t_j - 1)
A[i+1] = key
c8 n-1
t_j is the number of times the while loop is executed for that value of j.
t(n) = c1 n + c2(n-1) + c4(n-1) + c5 sum j=2 to n (t_j) +
c6 sum j=2 to n (t_j - 1) + c7 sum j=2 to n (t_j - 1)
+ c8(n-1)
Best case, input is already sorted
t_j = 1 for j = 2,3,...
t(n) = c1 n + c2(n-1) + c4(n-1) + c5(n-1 ) + c8(n-1)
= (c1 + c2 + c4 + c5 + c8)n - (c2 + c4 + c5 + c8)
= an + b
Worst case, reverse sort order
t(n) = c1 n + c2(n-1) + c4(n-1) + c5 sum j=2 to n (t_j) +
c6 sum j=2 to n (t_j - 1) + c7 sum j=2 to n (t_j - 1)
+ c8(n-1)
use some identities:
sum j=2 to n (j) = n(n+1)/2 - 1
sum j=2 to n (j-1) = n(n-1)/2
t(n) = c1 n + c2(n-1) + c4(n-1) + c5(n(n+1)/2 - 1) +
c6(n(n-1)/2) + c7 (n(n-1)/2) + c8(n-1)
= (c5/2 + c6/2 + c7/2) n^2 +
(c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8)n - (c2
+ c4 + c5 + c8)
= an^2 + bn + c
We will show an analysis of a recursive program.
divide-conquer approach
merge-sort(A,p,r)
if p<r
then q = floor( (p+r)/2 ) // p <=
q < r
merge-sort(A,p,q)
merge-sort(A,q+1,r)
merge(A,p,q,r)
call merge-sort(A,1,length(A)). merge takes time big-theta(n) n = r - p + 1
divide problem into 'a' subproblems of size 'b' each
D is dividing time
C is combining time
t(n) = big-theta(1) if n <= c
at(n/b) + D(n) + C(n) otherwise
big-theta(1) is a constant time
Analysis assume size is the power of 2
D(n) = big-theta(1)
time for subproblems = 2 t(n/2)
C(n) = big-theta(n) // merge
t(n) = big-theta(1) if n <= c
2 t(n/2) + big-theta(1) + big-theta(n)
The solution of the above recurrent equation is : t(n) = big-theta(n lg n)
lower bound of comparison sort
decision tree
binary tree , for sorting n items the leaves are n!
Thm : the height is big-ohmega(n lg n)
Proof
h = height
n! <= 2^h
h >= lg(n!)
n! > (n/e)^n
h >= lg(n/e)^n
h >= n lg n - n lg e
h = big-omega(n lg n)
In this case, we have proof that the merge-sort algorithm is optimal because it is as good as the lower-bound of the problem. (sorting by comparison).
lg denotes log_2
log denotes log_10
some property:
log_a x = log_b x / log_b a
log^2 n = (log n)^2 != log log n
lg * n is the number of times in taking log until the value
<= 1
(see def. in CLR p.36 iterated log function)
lg* 65536 = 4
lg 65536 = 16
lg 16 = 4
lg 4 = 2
lg 2 = 1