Follow Me

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