Antoun J. Yaacoub Ph.D.

Asymptotic Analysis exercises in C Programming in C

Asymptotic Analysis 1: What is the running time of the following piece of code ? for(inti=0;i<n*n;i++) sum=sum-i;...
Asymptotic Analysis 2: What is the running time of the following piece of code ? i=1;while(i<=n){ j=1; while(j<=n) j=j*2; i=i+1;}...
Asymptotic Analysis 3: What is the running time of the following piece of code ? for(i=1;i<=n;i++){ j=1; while(j<=n) j=j*2;}...
Asymptotic Analysis 4: What is the running time of the following piece of code ? int sum=0,a=0,i=0;while(i<n){ a=0; while(a<i) { sum++; a++; } i++;}...
Asymptotic Analysis 5: What is the running time of the following piece of code ? int i=1, s=1; while(s<=n){ i++; s+=i;}...
Asymptotic Analysis 6: What is the running time of the following piece of code ? int i, count =0;for(i=1;i*i<=n;i++) count++;...
Asymptotic Analysis 7: What is the running time of the following piece of code ? int i,j,k, count =0;for(i=n/2;i<=n;i++) for(j=1;j+n/2<=n;j=j++) for(k=1;k<=n;k=k*2) count++;...
Asymptotic Analysis 8: What is the running time of the following piece of code ? int i,j,k, count =0;for(i=n/2;i<=n;i++) for(j=1;j<=n;j=2*j) for(k=1;k<=n;k=k*2) count++;...
Asymptotic Analysis 9: What is the running time of the following piece of code ? void function(int n){ if(n==1) return ; for(int i=1; i<=n; i++) for(int j=1; j<=n;j++) break;} ...
Asymptotic Analysis 10: What is the running time of the following piece of code ? void function(int n){ for(int i=1; i<=n; i++) for(int j=1; j<=n;j+=i) printf("1");}...
Asymptotic Analysis 11: What is the running time of the following piece of code ? void function(int n){ for(int i=1; i<=n; i++) for(int j=1; j<=n;j*=2) printf("1");}...
Asymptotic Analysis 12: What is the running time of the following piece of code ? void function(int n){ for(int i=1; i<=n/3; i++) for(int j=1; j<=n;j+=4) printf("1");}...
Asymptotic Analysis 13: What is the running time of the following piece of code ? void function(int n){ int i =1; while(i<n){ int j=n; while(j>0) j/=2; i*=2; }}...
Asymptotic Analysis 14: What is the running time of the following piece of code ? int power(int b, int n){ int p=1, q=b, m=n; while(m>0) { if(m%2!=0) p*=q; m/=2; q*=q; ...
Asymptotic Analysis 15: What is the running time of the following piece of code ? for(i=n; i>0; i/=2){ for(j=1; j<n; j*=2) { for(k=0; k<n; k+=2) sum=sum+1; }} ...
Asymptotic Analysis 16: What is the running time of the following piece of code ? for(k=1; k<=n; k*=2){ for(i=0; i<k; i++) { for(j=0; j<n; j+=2) sum=sum+1; for(j=1; j<n; j*=2) ...
Asymptotic Analysis 17: What is the running time of the following piece of code ? for(i=1; i<=n; i++){ res=x+y+x+res; if((T[i]+k)<b) for(j=1; j<=n; j++) res=res+T[j]; else res=res+T...
Asymptotic Analysis 18: What is the running time of the following program? int C, N, R0, R1, I; void A(int R){ int I; for(I=1;I<=N;I++) R=R*I;} void B(int R){ int I, J; J=1; for(I=1;I<=N;I++) { ...
Asymptotic Analysis 19: We can write a function that finds all the prime numbers less than \texttt{n} using the sieve of Eratosthenes: Start Put numbers from 2 to n in a sieve (array) Repeat Select and remove from the sieve the smallest integer ...
Asymptotic Analysis 20: Without performing any calculations, give the worst case time complexity of the following function. Justify your answer. void f(int k, int n){ int i; for (i=0; i< n && k >0; i++) k = k / 2;} ...
Asymptotic Analysis 21: Without performing any calculations, give the worst case time complexity of the following function. Justify your answer. void f(int n, int m, int L){ int i=k=1, j=m; while((i<=n && j>=1) || k<=L) { �...
Asymptotic Analysis 22: Give the worst case time complexity of the following two functions. Justify your answer. void function1(int n){ int i, k, sum=0; for(i=0; i<n; i++) if(i<n/2) sum=sum+1; else �...
Complexity of sum of square root: Calculate and justify the time complexity of the following function:int f(int n){ int j = 10 ; while (j < n) { j += sqrt(j); } return j;}...

Back to the list of exercises

Select your ad blocker:

Disable AdBlock:

Disable AdBlock Plus:

Disable Adguard AdBlocker:

Disable uBlock Origin:

Asymptotic Analysis exercises in C Programming in C