Big-O Estimations

last updated 1/7/08

These exercises are borrowed from Headington/Riley, Data Abstraction and Structures Using C++, DC Heath, 1994.

Estimate the big-O complexity for each of the code segments below. Assume all variables are of type int. Assume also that N is the size of the data set.

  code segment big-O complexity
a. 

for (i=1; i<=N; i++){
    for (j=1; j<=N; j++){
       // 3 assignment statements
    }
}
 
b. 
for (i=1; i<=N; i++){
    // 2 assignment statements
    for (j=10; j<=N; j++){
       // 3 assignment statements
    }
}
  
c. 
for (i=1; i<=N; i++){
    // 2 assignment statements
    for (j=10; j<=N; j++){
        for(k=N; k>0; k--){
          // 3 assignment statements
        }
    }
}
  
d. 
for (i=1; i<=N; i++){
    // 2 assignment statements
    for (j=10; j<=N; j++){
         //20 assignments
    }
    for(j=1; j<=N; j++){
      if(j%2==1)
        for(k=N; k>0; k--){
          // 3 assignment statements
        }
    }
}
  
e. 
for (i=1; i<=N; i++){
    // 2 assignment statements
    for (j=10; j<=N; j++){
          // 3 assignment statements
    }
    if(i % 2 ==0){
          //4 assignments
    }
}
  
f. 
for (i=1; i<=N; i++){
    for (j=10; j<=A; j++){
        for(k=1; k<N; k++){
          // 3 assignment statements
        }
    }
}
  
g. 
for (i=1; i<=N; i++){
    for (j=1; j<=N-10; j++){
          // 3 assignment statements
      }
}
  
h. 
for (i=1; i<=N; i++){
    for (j=1; j<=i; j++){
          // 3 assignment statements
      }
}
  
i. 
i=1;
while(i<=N){
    // 4 assignments
    j=1;
    while(j <=N) {
       // 2 assignments
       j++;
    }
    i++;
}
  
j. 
i=1;
while(i<=N){
    // 4 assignments
    j=11;
    while(j <=99) {
       // 2 assignments
       j++;
    }
    i++;
}
  
k. 
i=1;
while(i<=N){
    // 4 assignments
    j=i;
    while(j >i) {
       // 2 assignments
       j--;
    }
    i++;
}
  
l. 
i=1;
while(i<=N){
    // 4 assignments
    j=1;
    while(j <=N) {
       // linear time task
       j++;
    }
    i++;
}
  
m. 
i=1;
while(i<=N){
    // 4 assignments
    j=1;
    while(j <=N) {
       // 2 assignments
       j=j*2;
    }
    i++;
}
  
n. 
i = N;
while(i >=1 ){
    // 4 assignments
    j=1;
    while(j <=N) {
       // 2 assignments
       j=j+2;
    }
    i /= 3;
}
  
o. 
void RecA (int N){
  //task requiring constant time
  if(N > 0)
       RecA(N-1)
}
  
p. 
void RecB (int N){
   int i;
   for(i=1; i <=N; i++) {
      //constant time task
   }
   if (N > 1)
        RecB(N-1);
 }
  
q. 
void RecB1 (int N){
   int i;
   for(i=1; i <=N; i++) {
      //linear time task
   }
   if (N > 1)
        RecB1(N-1);
 }
  
r. 
void RecC(int N){
   int i;
   for(i=1; i <=N; i++) {
    //constant time task
   }
   if(N > 1)
      RecC(N/2);
}