MERGE (A, p, q, r)
1 n1 =
q-p+1
2 n2 = r-q
3 // create
left and right arrays
4 for
i=1 to n1
5 L[i] = A[p+i-1]
6 for
i=1 to n2
7 R[i] = A[q+i]
8 L[n1+1]
= max_int
9 R[n2+1]
= max_int
10 i=1
11 j=1
12 for
k=p to r
13 if L[i] <= R[j]
14 A[k]=L[i]
15 i = i+1
16 else
17 A[k]=R[j]
18 j = j+1
The main merge sort procedure sorts elements in the subarray A[p..r]:
MERGE-SORT-RUN (A, p, r)
1 if p<r
2 q = ceil((p+r)/2)
3 MERGE-SORT-RUN(A,p,q)
4 MERGE-SORT-RUN(A,q+1,r)
5 MERGE(A,p,q,r)
Finally, the merge sort algorithm simply runs the main procedure on an array A[1..n]:
MERGE-SORT (A, n)
1 MERGE-SORT-RUN(A,1,n)
Assume T(n) is the running time of a size n problem. If the size is small (n<c), we assume it takes constant time to solve it. Also assume the following:
The recurrence is:
Q(1), if n <= c
T(n) =
aT(n/b)+D(n)+C(n)
We assume the original problem's size n=2x.
Hence:
Q(1), if n = 1
T(n) =
2T(n/2)+ Q(n)
At each step we need cn time to solve a problem. There lgn such steps, therefore:
T(n) = Q(nlgn)
The notations are defined in terms of functions whose domains are the set of natural numbers N={0,1,2,...}. Such notations are convenient for describing the worst-case running time function T(n).
For a given function g(n) we denote by Q(g(n)) the set of functions:
Q(g(n)) = {f(n) : $ c1,c2,n0 > 0 (" n>= n0 (0 <= c1g(n) <= f(n) <= c2g(n)))}
f(n) = Q(g(n)) º f(n) Î Q(g(n))
g(n) is an asymptotically tight bound for f(n)
Example 1:
(n/100+100) = Q(n)
Find c1, c2, n0 such that
c1n <= n/100+100<=c2n for all n>=n0
c1 <= 1/100 + 100/n <= c2
For n=n0=1 we have:
c1 <= 100 + 1/100
c2 >= 100 + 1/100
Choose c1 = 1/100; c2= 100.001, then the above equation will hold for any n>=1.
Example 2:
1000 <> Q(n)
By contradiction, suppose there is c1 so that
c1n <= 1000 for all n>=n0
n <= 1000/c1, which cannot hold for arbitrarily large n since c1 is constant.
We use O-notation when we have only an asymptotic upper bound:
O(g(n)) = {f(n) : $ c,n0 > 0 (" n>= n0 (0 <= f(n) <= cg(n)))}
Note that, Q(g(n)) Í O(g(n))
For example, n = O(n2).
Since O-notation describes an upper bound, when we use it to bound the worst-case running time of an algorithm, we have a bound on every input. For example, the O(n2) bound on the insertion sort also applies to its running time on every input However, Q (n2) on the insertion sort would only apply to the worst-case input. We saw when the input is sorted the running time is linear.
W-notation provides an asymptotic lower bound n a function:
W (g(n)) = {f(n) : $ c,n0 > 0 (" n>= n0 (0 <= cg(n) <= f(n)))}
Since W-notation describes a lower bound, it is useful when applied to the best-case running time of algorithms. For example, the best-case running time of the insertion sort is W(n), which implies that the running time of insertion sort W(n).
This notation is used to denote an upper bound that is not asymptotically tight:
o(g(n)) = {f(n) : "c > 0 ($ n0>0 (0 <= f(n) <= cg(n) for all n>n0))}
For example, 2n = o(n2). Intuitively:
lim f(n)/g(n) = 0
We use w-notation to denote a lower bound that is not asymptotically tight:
w (g(n)) = {f(n) : "c > 0 ($ n0>0 (0 <= cg(n) <= f(n) for all n>n0))}
For example, n2/2 = w (n). The relationship implies:
lim f(n)/g(n) = ¥