Algorithms
Contents
CH1 : Analyzing the complexity of Algorithms
CH2 : Sorting Algorithms
A - Internal Sorting Algorithms
1- Bubble Sort
2- Insertion Sort
3- Selection Sort
4- Quick Sort
5- Merge Sort
6- Heap Sort
B- External Sorting Algorithms
1- Balanced Merge Sort
2- PolyPhase Sort
CH3 : Graph Algorithms ( Shortest Path Algorithms )
1- Dijkstra's Algorithm
2- Greedy's Algorithm
3- Floyd's Algorithm
4- Modified Floyd's Algorithm
CH4 : Spanning Tree Algorithms
1- Boruvka's Algorithm
2- Kruskal's Algorithm
3- Prim's Algorithm
CH5 : Storing in Binary Search Tree ( AVL Tree )
CH6 : Storing in Multy Way Search Tree
1- B-Tree Algorithms
2- B*-Tree Algorithms
CH7 : Hashing Algorithms
Algorithm: A finite sequence of instructions for solving a problem.
** Two-Reasons to choose an Algorithm:
1. Human Reason :
To understand and implement the algorithm.
2. Machine Reason :
Time , Space.
Cost of algorithm :
Cost = (Cost of understanding and programming + Cost of running the program)
= Software Cost + Hardware Cost
Hardware Cost = (Cost of running program once ) * number of execution
( Choosing the algorithm is dependent on the cost of the algorithm )
** How do you compare the efficiency of two algorithms ( for one problem ) ?
1. Compare the execution time.
2. Compare the size of program or (algorithm)
Size of program or algorithm is dependent on :
- The number of lines.
- The number of instructions.
** It’s better \
to measure the complexity of algorithm, that means (count number of basic
operations).
Type of Basic Operations :
1. By Searching (Comparing or logical operations )….[ < , <= , ≠ , > , >= , == ]
2. By arithmetic operations [ + , - , * , / , % , ++ , -- , ^ , *= , ….]
Three types to determine cost of algorithm :-
1. Worst case complexity
2. Best case complexity
3. Average case complexity
Suppose n >= 0 (The size of input) :
1. Best case complexity :
n >= 0 , I (instances of problem) define :
B(n) = the minimum value of T(I) ,
where T(I) the number of basic operations for instance I.
( B(n) the Best case complexity of the algorithm )
2. Worst case complexity :
n >= 0 , I (instances of problem) define :
W(n) = the maximum value of T(I) ,
where T(I) the number of basic operations for instance I.
( W(n) the worst case complexity of the algorithm )
3. Average complexity :
A(n) = ∑ ( ) ( )
Where P(I) is the probability that the instance I will occur and
T(I) the number of basic operations for instance I.
Two ways to define the notation of complexity of an algorithm to solve a class of
problems (Worst or Average case copmlexity ) :
Examples :
Example1 - Meaning of Instance I :
Suppose we have a one dim array length 10 containing different int keys
19 22 13 45 34 31 100 90 75 60
1 2 3 4 5 6 7 8 9 10
Problem : Searching a given key
Algorithm : Sequential Searching
There are 11 Instances of this problem :
I1 : Find first T(I1) = 1 B.O.
I2 : Find second T(I2) = 2 B.O.
I3 : Find third T(I3) = 3 B.O.
…
….
I10 : Find Last T(I10) = 10 B.O.
I11 : Not found T(I11) = 10 B.O.
Best case complexity = B(n) = B(10) = 1 B.O.
Worst case complexity = W(n) = W(10) = 10 B.O.
Average case complexity =
A(n) = A(10) = ∑ ( ) ( ) = (1/11)*1 + (1/11)*2 + ...+(1/11)*10 +
(1/11)*10 = ?
Example2 :
Analyze and find the worst case complexity of the following algorithm :
t=1;
while ( t <= n ) // n is the input size
{
for ( int i = 1 ; i < n ; ++i )
{
Add += i % t ;
for ( int j = n ; j > 1 ; --j )
P = P *3 ;
}
if ( X > 2)
S.O.P(Y - 1);
t = t + 1;
Basic Op Count
<= N
< n2
++ n2
+= n2
% n2
> n3
-- n3
* n3
> N
- <= n
+ N
W(n) = 4n + 4n2 + 3n3
Example3 :
Given following :
Problem with input size n ∞?
solved
Algorithm1 (P1) Algorithm2 (P2)
W1(n) = 100n W2(n) = 4n2
Two algorithms P1, P2 for solving the same problem with W1 , W2 as worst case
complexities of both algorithms :
P1 : W1(n) = 100n
P2 : W2(n) = 4n 2
1. suppose the input size : n < 25
n= 1 W1(n) = 100n = 100 B.O. , W2(n) = 4n2 = 4 B.O.
In this case it’s better to use P2
n= 2 W1(n) = 100n = 200 B.O. , W2(n) = 4n2 = 16 B.O.
In this case it’s better to use P2 than P1
n= 3 W1(n) = 100n = 300 B.O. , W2(n) = 4n2 = 36 B.O.
In this case it’s better to use P2 than P1
……..
…….
n = 24 W1(n) = 100n = 2400 B.O. , W2(n) = 4n2 = 2304 B.O.
In this case it’s better to use P2 than P1
2. Suppose the input size : n = 25
W1(n) = 100n = 2500 B.O. , W2(n) = 4n2 = 2500 B.O.
In this case P1 and P2 are same
3. suppose the input size : n > 25
n= 26 W1(n) = 100n = 2600 B.O. , W2(n) = 4n2 = 2704 B.O.
W2(n) > W1(n)
In this case it’s better to use P1 than P2
In general :
n : P1 better than P2 , ( using the same computer )
Definitions :
f , g : N R\ {0} ( Two positive real valued functions ) Then :
1. g(n) is O(f(n)) ( read: g(n) is big O of f(n) )
k R\{0}, n0 N such that
g(n) ≤ k * f(n) n ≥ n0
2. g(n) is Ω (f(n)) ( read: g(n) is big Omega of f(n) )
k R\{0}, n0 N such that
g(n) k * f(n) n ≥ n0
3. g(n) is (f(n)) ( read: g(n) is big Theta of f(n) )
k1 , k2 R\{0}, n0 N such that
k1*f(n) ≤ g(n) ≤ k2 * f(n) n ≥ n0
** if g(n) is O(f(n)) but f(n) is not O(g(n)) O(g(n)) better than O(f(n)).
That means an algorithm with worst case complexity g(n) runs faster than one with
worst case complexity f(n)
an algorithm is efficient W(n) is O(nk) , where k N\{0}.
Examples :
Ex1 :
Given two positive real functions W1(n) and W2(n) , where
W1(n) = 100n and W2(n) = 4n2
Question : W1(n) is O(W2(n)) ? or
W2(n) is O(W1(n)) ?
W1(n) is O(W2(n)) ?
Solution :
Suppose k = 1 and n0 = 25 , g(n) = W1(n) and f(n) = W2(n)
g(n) ≤ k*f(n) ? n ≥ n0
W1(n) ≤ 1*W2(n) ? n ≥ 25
100n ≤ 1*4n2 ? n ≥ 25
25 ≤ n ? Yes n ≥ 25
W1(n) is O(W2(n))
W2(n) is O(W1(n)) ?
Solution :
Suppose k = 1 and n0 = 25 , g(n) = W2(n) and f(n) = W1(n)
g(n) ≤ k*f(n) ? n ≥ n0
W2(n) ≤ 1*W1(n) ? n ≥ 25
4n2 ≤ 100n ? n ≥ 25
n ≤ 25 ? NO n ≥ 25
W2(n) is NOT O(W1(n)) W2(n) is Ω (W1(n))
Ex2 :
W2(n) is Ω (W1(n)) ?
Solution :
Suppose k = 1 and n0 = 25 , g(n) = W2(n) and f(n) = W1(n)
g(n) ≥ k*f(n) ? n ≥ n0
W2(n) ≥ 1*W1(n) ? n ≥ 25
4n2 ≥ 100n ? n ≥ 25
n ≥ 25 ? YES n ≥ 25 W2(n) is Ω (W1(n))
Try with other values for k and n0 , e.g. k = 1/2 and n0 = 50 ….
Other Definitions ( using limit ) :
f , g : N R\ {0} ( Two positive real valued functions ) Then :
1. g(n) is O(f(n)) ( ) ( )=c,
where c ≥ 0 , c nonnegative real number c R+
2. g(n) is Ω(f(n)) ( ) ( )=c,
where c>0 , strictly positive real number
OR ( ) ( )=∞
3. g(n) is (f(n)) ( ) ( )=c
where 0 < c < ∞ , c positive real number
** If lim g(n) / f(n) = c , c positive real number :
lim f(n)/ g(n) = 1/c , 1/c > 0
g(n) is O(f(n)) and f(n) is O(g(n))
** If lim g(n) / f(n) = 0
g(n) is O(f(n)) but f(n) is not O(g(n))
g(n) is better than f(n)
Examples : ( classes of positive real functions)
1. Infinite constant functions (like g(n) = 1/2 , = 1/5 , = 7.5 , = 10000 , 1020 , ….)
2. Infinite log functions ( Like g(n) = log2n , 3.5*log2n , 10000*log2n , 5*log2n+1000 -9.5 , … )
3. Infinite linear functions (Like g(n) = 100*n , ….. )
4. Infinite linear log functions ( Like g(n) = 7*n*log2n , …. )
5. Infinite polynomial functions ( like g(n) = n2 , n3 , n5 , 15*n4 – n*log2n , …..)
6. Infinite expontial functions ( Like g(n) = 2n , 3n , ….)
1. lim ( any constant function) / log2(n) = 0 , likes g(n) = 1/2 ,g(n) = 1000 , g(n) = 10200
2. lim ( log2 (n) / n ) =0
3. lim (n / (n*log2 (n)) ) = 0
4. lim ((n*log2 (n)) / n2) = 0
5. lim ( np / nq ) =0 … If ( p < q ) and p , q >= 3
6. p n
lim ( n / 2 ) =0 … positive integer indices p
Efficiency of algorithms :
1. O(1) [ constant functions ] is better than O(log2n)
2. O( log2 n) [log functions ] is better than O(n)
3. O( n) [ linear functions ] is better than O(n log2n)
4. O( n log2n) [ log linear functions ]is better than O(n2)
5. O( np) [ polynomial functions ] is better than O(nq) … if ( p < q) and p,q >= 2
6. O( np) [Expontial functions ] is better than O(2n) … positive integer indices p
OR : \
O(1) < O( log2n) < O(n) < O( n log2n) < O(n2) < O(np) (p > 2) < O(2n) .
Example : (Calculation of complexity of algorithms)
Given following :
Problem with input size n ∞?
solved
Algorithm1 (P1) Algorithm2 (P2)
W1(n) = 100n W2(n) = 4n2
Two algorithms P1, P2 for solving the same problem with W1 , W2 as worst case
complexities of both algorithms :
P1 : W1(n) = 100n
P2 : W2(n) = 4n 2
Which algorithm is better to use than the other ?
P1 : W1(n) = 100n
lim W1(n)/n = lim 100n/n = 100 ≠ ∞ W1(n) is O(n)
P2 : W2(n) = 4n 2
lim W2(n)/n2 = lim 4n2/n2 = 4 ≠ ∞ W2(n) is O(n2)
Problem with input size n ∞?
solved
Algorithm1 (P1) Algorithm2 (P2)
W1(n) = 100n W2(n) = 4n2
W1(n) is O(n) W2(n) is O(n2)
It is better to use P1 than P2 for all cases
Example :
Suppose we have an algorithm P with worst case complexity W(n) ,
Every basic operation costs ,
T the used time to run the algorithm for the input n ,
T = W(n)*
when we solve the equation , we can know the maximum size , which can be handled
in T .
Examples :
Ex1 :
Suppose τ
= 1 ms ,
W(n) = n2 ,
T = 1 hour
T = W(n)*
60*60 = n2 * 10-3
n2 = 6* 105
n = 600 * √ 10 ≈ 1897 input size
Ex2 :
Given an algorithm with W(n) = 2n runs on two different machines so that the time
for execution a basic operation for the first machine equal to and for the other one
equal to /k , where k >= 2.
Calculate n1 , n2 maximum input size for two machines which can be handled in T time
(Same time interval)
Problem?
Solved
Algorithm
W(n) = 2n
Make a program
Runs on two different machines (Computers) using the same time interval
comp1 with speed = comp2 with speed = /k , k > 1
calculate n1 claculate n2
Solution :
Using the equation T = W(n)*
T = W(n1)*
T = /k*W(n2)
W(n1)* = T = /k*W(n2)
W(n2) = k*W(n1)
Now we have the complexity W(n) = 2n
W(n2) = k*W(n1)
n
2 2 = k*2n1 | log2
n2
log2(2 ) = log2(k*2n1)
n2 = log2k + n1
n2 > n1 .
