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;}...
Dealing with Logs: Given that $ \log_{10}4 = 0.6020 $ and $ \log_{10}5 = 0.6989 $ , find the value of $ \log_{20}10 $....
Series Sum: Compute the sum of the following series: $ \sum_{i=1}^n i \times 2^i$....
Series Sum 2: Compute the sum of the following series: $ \sum_{i=1}^n i^2 \times 2^i$....
Series Sum 3: Which of the following two terms is larger: $ \sum_{i=1}^n i^2 $ or $ \sum_{i=1}^{n^2} i $....
Asymptotic Analysis 23: Give the worst case time complexity of the following function. Justify your answer. i = 1;while (i < n) { j = 2; while (j < n) j = j * j; i++;} ...
Asymptotic Analysis 24: How do these pairs of functions compare asymptotically: $$n^{17}$$ and $$2^n$$ $$2^{n^2}$$ and $$10^n$$ ...

Back to the list of exercises