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 ? 5Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!