Course Name: CS302-Design an
analysis of Algorithm
Credit Hours: 3
Week 3
Department of Computer Science | FAST-NU 1
Task
1) 2n2= Ω (n3) True or False?
2) If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n)
= g(n) True or false?
3) If f(n) = O(g(n)) and g(n) = O(h(n)), then
h(n) = Ω(f(n)) True or false?
4) n/100= Ω(n) True or False?
5) Let f(n) = and g(n) = n2. f(n) = Θ(g(n)).
Solution
1-false
2-false n n+1
3-true a<b; b<c ; a<C Transitive relation
4-true c>(1/100)
5-true
Important Summations that should
be Committed to Memory.
O(Logn) Time Complexity of a loop is considered
as O(Logn) if the loop variables is divided /
multiplied by a constant amount.
Here c is some positive integer
for (int i = 1; i <=n; i *= c)
{ // some O(1) expressions }
for (int i = n; i > 0; i /= c)
{ // some O(1) expressions }
Example (Dependent nested
loop)
For (i=1;i<=n;i++)
{For(j=i; j<=n;j++)
{
//sequence of statements
}
}
Arithmetic series
n+ (n-1) +(n-2)+……1= n(n+1)/2 =O(n2)
Task
Design nested loop in which execution of inner
instructions sum to quadratic series.
For (i=1;i<=n;i++)
for (j=1;j<=i2; j++)
{ //sequence of statements
}
1+4+9+…..n2
= 2n3+3n2+n / 6
= O(n3)
Example (Nested loop)
for (int i = 1; i <=n; i *= 2)
{
for (int j = 1; j <= n; j *= 4)
{ // some O(1) expressions }
}
log base 2 n * log base 4 n
=O(log n)2
Example
int fun()
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
Explanation: For a input integer n, the
innermost statement is executed following times.
n + n/2 + n/4 + … 1
= O log(n)
Task:
int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
“count = count + 1”
0 + 1 + 2 + 3 + 4 + …. + (n-1) times.
=
=(n-1)(n-1+1)/2
=(n-1)(n)/2
=O(n2)
Previous Lecture Example
for (i=0; i<n; i++)
{for (j=i; j<n;j++)
{
Sequence of statements….
}
}
n + (n-1 ) + (n-2) +…… 2+1
=
=n(n+1)/2
=O(n2)
Recurrence
Relations
Department of Computer Science | FAST-NU 15
What is a recurrence relation?
A recurrence relation, T(n), is a recursive function of integer variable
n.
Like all recursive functions, it has both recursive case and base case.
Example:
The portion of the definition that does not contain T is called the base
case of the recurrence relation
The part that contains T is called the recurrent or recursive case.
Forming Recurrence Relations
For a given recursive method, the base case and the recursive case of its recurrence
relation correspond directly to the base case and the recursive case of the method.
Example 1: Write the recurrence relation for the following method.
public void f (int n) {
if (n > 0) {
[Link](n);
f(n-1);
}
}
The base case is reached when n == 0. The method performs one
comparison. Thus, the number of operations when n == 0, T(0), is
some constant a.
When n > 0, the method performs two basic operations and then calls
itself, using ONE recursive call, with a parameter n – 1.
Therefore the recurrence relation is:
Forming Recurrence Relations
Example 2: Write the recurrence relation for the following method.
public int g(int n) {
if (n == 1)
return 2;
else
return 3 * g(n / 2) + g( n / 2) + 5;
}
The base case is reached when n == 1. The method performs one
comparison and one return statement. Therefore, T(1), is constant c.
When n > 1, the method performs TWO recursive calls, each with the
parameter n / 2, and some constant # of basic operations.
Hence, the recurrence relation is:
Solving Recurrence Relations
Methods to solve recurrence relations that represent the running time of
recursive methods:
Iteration method (unrolling and summing)
Recursion tree method
Master method
1
Iteration Method
Department of Computer Science | FAST-NU 20
Iteration Method
Back Substitution method
unrolling and summing
Iteration consist of repeatedly substituting the
recurrence into itself to obtain an summation
expression
Analysis Of Recursive Factorial method
Example2: Form and solve the recurrence relation for the running time
of factorial method and hence determine its big-O complexity:
long factorial (int n) {
if (n == 0)
T(0) = c return 1;
T(n) = b + T(n - 1) else
= b + b + T(n - 2) return n * factorial (n – 1);
= b +b +b + T(n - 3)
}
…
= kb + T(n - k)
When n-k = 0, we have: n=k
T(n) = nb + T(n - n)
= bn + T(0)
= bn + c.
Therefore method factorial is O(n).
Analysis Of Recursive Binary Search
public int binarySearch (int target, int[] array,
int low, int high) {
if (low > high)
return -1;
else {
int middle = (low + high)/2;
if (array[middle] == target)
return middle;
else if(array[middle] < target)
return binarySearch(target, array, middle + 1, high);
else
return binarySearch(target, array, low, middle - 1);
}
}
The recurrence relation for the running time of the method is:
T(1) = a if n = 1 (one element array)
T(n) = T(n / 2) + b if n > 1
Analysis Of Recursive Binary Search
Expanding:
T(n) = T(n / 2) + b
= [T(n / 4) + b] + b = T (n / 22) + 2b
= [T(n / 8) + b] + 2b = T(n / 23) + 3b
= ……..
= T( n / 2k) + kb
When n / 2k = 1 n = 2k k = log n, we have:
T(n) = T(1) + b log n
= a + b log n
Therefore, Recursive Binary Search is O(log n)
Task
T(n) = T(n-1) + bn
T(0) = c
T(n) = T(n-1) + bn
= (T(n-2) + b(n-1)) + bn = T(n-2) + bn+bn-b
= T(n-3) + b(n-2)) +b(n-1) + b(n) =T(n-3)+3bn-2b-b
= T(n-4) + b(n-3)+ b(n-2)) +b(n-1) + b(n) = T(n-4)+4bn-3b-2b-b
=T(n-4)+4bn-b[3+2+1]
= T(n-k)+kbn-b{(k-1) (k-1)/2}
n-k=0 => n=k
= T(0)+bn^2+b[(n-1)(n-1)/2]
=c+ bn^2+b[(n-1)(n-1)/2]
=O(n^2)
2
Recursion Tree Method
Recursion tree method
solving recurrences
expanding the recurrence into a tree
summing the cost at each level
Difference between depth and height of node
Recursion tree
Solve T(n) = 2T(n/2) + c n, where c > 0 is constant.
T(n)
Here Tree nodes represent costs incurred at
various levels of the recursion
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2) T(n/2)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
cn/4 cn/4 cn/4 cn/4
O(1)
Determining depth/height of tree
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
h = log n cn/4 cn/4 cn/4 cn/4
O(1)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2
h = log n cn/4 cn/4 cn/4 cn/4
O(1)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = log n cn/4 cn/4 cn/4 cn/4
O(1)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = log n cn/4 cn/4 cn/4 cn/4 cn
…
O(1)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = log n cn/4 cn/4 cn/4 cn/4 cn
…
O(1) #leaves = n O(n)
Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = log n cn/4 cn/4 cn/4 cn/4 cn
…
O(1) #leaves = n O(n)
Total = O(n log n)
Let's consider another example,
T(n) = T(n/3) + T(2n/3) + n.
Expanding out the first few levels, the recurrence
tree is:
the closed form of this recurrence is O(n log n).
Determining Height of tree
Home Task
Solve T(n) = 2T(n/2) + n2:
Master Theorem
Time Complexity of merge sort
Master Theorem
Time Complexity of merge sort
Time Complexity of merge sort
T (n) = 3T (n/2)+ n^2
T (n) = Θ(n^2) (Case ?)
T (n) = 4T (n/2)+ n^2 T (n) = Θ(n^2 log n) (Case ?)
T (n) = 2T (n/2)+ n log n T (n) = n log^2 n (Case ?)
T (n) = 3T (n/2)+ n
T (n) = Θ(n^lg 3) (Case ?)
Time Complexity
You cannot use the Master Theorem if
T(n) is not monotone, e.g. T(n) = sin(x)
f(n) is not a polynomial, e.g., T(n)=2T(n/2)+2^n
b cannot be expressed as a constant.
Time Complexity
measure of algorithm efficiency
has a big impact on running time.
Big-O notation is used.
To deal with n items, time complexity can be
O(1), O(log n), O(n), O(n log n), O(n2), O(n3),
O(2n), even O(nn).
(Divide:)split A down the middle into two
subsequences, each of size roughly n/2
(Conquer:) sort each subsequence by calling
merge sort recursively on each.
(Combine:) merge the two sorted
subsequences into a single sorted list
Algorithm Lecture by [Link] Fast-NU
Algorithm Lecture by [Link] Fast-NU
Algorithm Lecture by [Link] Fast-NU
Algorithm Lecture by [Link] Fast-NU
Merge Sort
The fundamental operation in this algorithm is merging
two sorted lists.
Because the lists are sorted, this can be done in one
pass through the input, if the output is put in a third list.
The basic merging algorithm takes
two input arrays: a and b,
an output array: c
three counters: aptr, bptr, and cptr,
which are initially set to the beginning of their respective arrays.
The smaller of a[aptr] and b[bptr] is copied to the next
entry in c, and the appropriate counters are advanced.
When either input list is exhausted, the remainder of
the other list is copied to c.
Algorithm Lecture by [Link] Fast-NU
Merge Sort
void m_sort( input_type a[], input_type tmp_array[ ], int left, int right )
{
int center;
if( left < right )
{
center = (left + right) / 2; Calculate the centre index of the input list
Recursively call the m_sort procedure
m_sort( a, tmp_array, left, center ); for the left-half of the input data
Recursively call the m_sort procedure
m_sort( a, tmp_array, center+1, right ); for the right-half of the input data
merge( a, tmp_array, left, center+1, right ); Merge the two sorted lists
}
}
Algorithm Lecture by [Link] Fast-NU
Merge Sort Example (recursive Function Calls)
Mergesort(a, 8)
m_sort( a, tmp_array, 0, 7 )
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
Merge(a, tmp_array, 0, 4, 7 )
m_sort( a, tmp_array, 0, 3) m_sort( a, tmp_array, 4, 7)
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
m_sort(0, 1) m_sort(2, 3 ) m_sort(4, 5) m_sort(6, 7 )
Merge(a, tmp_array, 0, 2, 3 ) Merge(a, tmp_array, 4, 6, 7 )
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
m_sort(0,0) m_sort(1,1) m_sort(2,2) m_sort(3,3) m_sort(4,4) m_sort(5,5) m_sort(6,6) m_sort(7,7)
Merge(0, 1, 1 ) Merge(2, 3, 3 ) Merge(4, 5, 5 ) Merge(6, 7, 7 )
Algorithm Lecture by [Link] Fast-NU
Merge Sort Example (Merging process)
Mergesort(a, 8)
m_sort( a, tmp_array, 0, 7 )
662(0)(0) 58 (1)
10 (1) 55 (2)
44 (2) 1045
(3)(3) 45 (4)
55 (4) 44 (5)
58 (5) 6 (6)(6)
62 90 (7)
90 (7)
Merge(a, tmp_array, 0, 4, 7 )
m_sort( a, tmp_array, 0, 3) m_sort( a, tmp_array, 4, 7)
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
m_sort(0, 1) m_sort(2, 3 ) m_sort(4, 5) m_sort(6, 7 )
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
Merge(a, tmp_array, 0, 2, 3 ) Merge(a, tmp_array, 4, 6, 7 )
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
m_sort(0,0) m_sort(1,1) m_sort(2,2) m_sort(3,3) m_sort(4,4) m_sort(5,5) m_sort(6,6) m_sort(7,7)
Merge(0, 1, 1 ) Merge(2, 3, 3 ) Merge(4, 5, 5 ) Merge(6, 7, 7 )
58 (0) 62 (1) 10 (2) 55 (3) 44 (4) 45 (5) 6 (6) 90 (7)
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
cptr
62 (0) 58 (1) 55 (2) 10 (3) 45 (4) 44 (5) 6 (6) 90 (7)
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2) 45 (3)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2) 45 (3) 55 (4)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2) 45 (3) 55 (4) 58 (5)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2) 45 (3) 55 (4) 58 (5) 62 (6)
cptr
Algorithm Lecture by [Link] Fast-NU
Merge two arrays
10 (0) 55 (1) 58 (2) 62 (3) 6 (4) 44 (5) 45 (6) 90 (7)
aptr bptr
6 (0) 10 (1) 44 (2) 45 (3) 55 (4) 58 (5) 62 (6) 90 (7)
cptr
Algorithm Lecture by [Link] Fast-NU
TASKS to DO
Department of Computer Science | FAST-NU
Coding example #1
for ( i=0 ; i<n ; i++ )
m += i;
Coding example #2
for ( i=0 ; i<n ; i++ )
for( j=0 ; j<n ; j++ )
sum[i] += entry[i][j];
Coding example #3
for ( i=0 ; i<n ; i++ )
for( j=0 ; j<i ; j++ )
m += j;
Coding example #4
i = 1;
while (i < n) {
tot += i;
i = i * 2;
}
Example #4: equivalent # of steps?
i = n;
while (i > 0) {
tot += i;
i = i / 2;
}
Coding example #5
for ( i=0 ; i<n ; i++ )
for( j=0 ; j<n ; j++ )
for( k=0 ; k<n ; k++ )
sum[i][j] += entry[i][j][k];
Coding example #6
for ( i=0 ; i<n ; i++ )
for( j=0 ; j<n ; j++ )
sum[i] += entry[i][j][0];
for ( i=0 ; i<n ; i++ )
for( k=0 ; k<n ; k++ )
sum[i] += entry[i][0][k];
Coding example #7
for ( i=0 ; i<n ; i++ )
for( j=0 ; j< sqrt(n) ; j++ )
m += j;
Coding example #8
for ( i=0 ; i<n ; i++ )
for( j=0 ; j< sqrt(995) ; j++ )
m += j;
Coding example #8 : Equivalent
code
for ( i=0 ; i<n ; i++ )
{
m += j;
m += j;
m += j;
…
m += j; // 31 times
}
Coding example #9
int total(int n)
for( i=0 ; i < n; i++)
subtotal += i;
main()
for ( i=0 ; i<n ; i++ )
tot += total(i);
Coding example #9: Equivalent
code
for ( i=0 ; i<n ; i++ ) {
subtotal = 0;
for( j=0 ; j < i; j++)
subtotal += j;
tot += subtotal;
}
Example to see