Reference no: EM132430748

Question: Calculating Complexity

a. What is the relationship between an algorithm's running time and its big-oh order of growth?

b. What are considered some "good" Big-Os and some "bad" Big-Os?

c. What are the Big-Os of the following algorithms?

Algorithm 1:

statement1;

if(condition1) {
   statement2;
} else {
   for(int i=0; i<n; i++) {
      statement3;
    }
   statement4;
}

Algorithm 2:

i=0;
while(i<n) {
   for(int j=i; j<n; j++) {
      statement1;
    }
   statement2;
   i++;
}

Algorithm 3:

for(int i=0; i<n; i++) {
   for(int j=0; j<n; j++) {
      if(condition1) {
         for(int k=0; k<10; k++) {
              statement1;
           }
      } else {
         statement2;
      }
   }
}

Algorithm 4:

for(int i=0; i<=n; i++) {
   for(int j=0; j<=n; j++) {
      if(j%2==0) {
         statement1
      }
   }
}

d. What are the Big-Os of the following algorithms?

Algortihm A:

for(int i=0; i<n; i++) 
   add i to the beginning of an array-based list

Algortihm B:

for(int i=0; i<n; i++) 
   add i to the end of an array-based list

Algortihm C:

for(int i=0; i<n; i++) 
   add i to the beginning of a linked list with only a head pointer

Algortihm D

for(int i=0; i<n; i++) 
   add i to the end of a linked list with only a head pointer