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++)
      path[i][j] = adjmat[i][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++)
      path[i][j] = adjmat[i][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++)
      path[i][j] = adjmat[i][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++)
      path[i][j] = adjmat[i][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
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Content Category

Related Searches

Summary

,

Exam

,

Extra Questions

,

ppt

,

pdf

,

Viva Questions

,

Semester Notes

,

past year papers

,

shortcuts and tricks

,

Sample Paper

,

practice quizzes

,

study material

,

video lectures

,

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

,

MCQs

,

Previous Year Questions with Solutions

,

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

,

mock tests for examination

,

Important questions

,

Objective type Questions

,

Free

,

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

;