Courses

# Asymptotic Complexity (Programming & Data Structures) Computer Science Engineering (CSE) Notes | EduRev

Created by: Smita Sharma

## Computer Science Engineering (CSE) : Asymptotic Complexity (Programming & Data Structures) Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

Dept. of CSE, IIT KGP
1
Asymptotic Complexity
CS10001: Programming & Data Structures
Pallab Dasgupta
Professor, Dept. of Computer
Sc. & Engg.,
Indian Institute of
Technology Kharagpur
Page 2

Dept. of CSE, IIT KGP
1
Asymptotic Complexity
CS10001: Programming & Data Structures
Pallab Dasgupta
Professor, Dept. of Computer
Sc. & Engg.,
Indian Institute of
Technology Kharagpur
Dept. of CSE, IIT KGP
2
Transitive Closure
Transclosure ( int adjmat[ ][max], int path[ ][max] )
{
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
for (k = 0; k < max; k++)
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
if ((path[i][k] == 1)&&(path[k][j] == 1)) path[i][j] = 1;
}
How many operations are performed?
Page 3

Dept. of CSE, IIT KGP
1
Asymptotic Complexity
CS10001: Programming & Data Structures
Pallab Dasgupta
Professor, Dept. of Computer
Sc. & Engg.,
Indian Institute of
Technology Kharagpur
Dept. of CSE, IIT KGP
2
Transitive Closure
Transclosure ( int adjmat[ ][max], int path[ ][max] )
{
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
for (k = 0; k < max; k++)
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
if ((path[i][k] == 1)&&(path[k][j] == 1)) path[i][j] = 1;
}
How many operations are performed?
Dept. of CSE, IIT KGP
3
Merge-Sort
void mergesort ( int a[ ], int lo, int hi )
{
int m;
if (lo<hi) {
m=(lo+hi)/2;
mergesort(a, lo, m);
mergesort(a, m+1, hi);
merge(a, lo, m, hi);
}
}
T(n)
T(n/2)
?
T(n/2)
Page 4

Dept. of CSE, IIT KGP
1
Asymptotic Complexity
CS10001: Programming & Data Structures
Pallab Dasgupta
Professor, Dept. of Computer
Sc. & Engg.,
Indian Institute of
Technology Kharagpur
Dept. of CSE, IIT KGP
2
Transitive Closure
Transclosure ( int adjmat[ ][max], int path[ ][max] )
{
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
for (k = 0; k < max; k++)
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
if ((path[i][k] == 1)&&(path[k][j] == 1)) path[i][j] = 1;
}
How many operations are performed?
Dept. of CSE, IIT KGP
3
Merge-Sort
void mergesort ( int a[ ], int lo, int hi )
{
int m;
if (lo<hi) {
m=(lo+hi)/2;
mergesort(a, lo, m);
mergesort(a, m+1, hi);
merge(a, lo, m, hi);
}
}
T(n)
T(n/2)
?
T(n/2)
Dept. of CSE, IIT KGP
4
Function Merge
void merge ( int a[ ], int lo, int m, int hi )
{
int i, j, k, b[MAX];
// copy both halves to auxiliary array b
for (i=lo; i<=hi; i++) b[i]=a[i];
i=lo; j=m+1; k=lo;
// copy back next-greatest element at each time
while (i<=m && j<=hi)
if (b[i]<=b[j]) a[k++]=b[i++];
else a[k++]=b[j++];
// copy back remaining elements of first half (if any)
while (i<=m) a[k++]=b[i++];
}
Page 5

Dept. of CSE, IIT KGP
1
Asymptotic Complexity
CS10001: Programming & Data Structures
Pallab Dasgupta
Professor, Dept. of Computer
Sc. & Engg.,
Indian Institute of
Technology Kharagpur
Dept. of CSE, IIT KGP
2
Transitive Closure
Transclosure ( int adjmat[ ][max], int path[ ][max] )
{
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
for (k = 0; k < max; k++)
for (i = 0; i < max; i++)
for (j = 0; j < max; j++)
if ((path[i][k] == 1)&&(path[k][j] == 1)) path[i][j] = 1;
}
How many operations are performed?
Dept. of CSE, IIT KGP
3
Merge-Sort
void mergesort ( int a[ ], int lo, int hi )
{
int m;
if (lo<hi) {
m=(lo+hi)/2;
mergesort(a, lo, m);
mergesort(a, m+1, hi);
merge(a, lo, m, hi);
}
}
T(n)
T(n/2)
?
T(n/2)
Dept. of CSE, IIT KGP
4
Function Merge
void merge ( int a[ ], int lo, int m, int hi )
{
int i, j, k, b[MAX];
// copy both halves to auxiliary array b
for (i=lo; i<=hi; i++) b[i]=a[i];
i=lo; j=m+1; k=lo;
// copy back next-greatest element at each time
while (i<=m && j<=hi)
if (b[i]<=b[j]) a[k++]=b[i++];
else a[k++]=b[j++];
// copy back remaining elements of first half (if any)
while (i<=m) a[k++]=b[i++];
}
Dept. of CSE, IIT KGP
Complexity of mergesort
T(0)= 1
T(n) = T(n/2) + n + T(n/2)
= 2T(n/2) + n
Rewrite n as 2x:
T(2x) = 2T(2x-1) + 2x
= 2T(2T(2x-2) + 2x-1) + 2x
= 22T(2x-2) + 2x + 2x
= x2x
Therefore: T(n)  n log2 n ?
5
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;