Question

Compute the total running time for each of the functions in the following code. First, compute the running time in terms of some constants a, b, c, d, e, etc. Show your work and give the answer in the text box. Then give the tightest big-O bound you can for each. (All of the functions are O(n!), but you can give a more informative bound for each.)

void f(int n) {

  int i = 1;

  while (i <= sqrt(n)) {

    if (n % i == 0 ) {

      printf("%d, %d\n", i, (n / i));

    }

    i += 1;

  }

}

int main() {

  f(36);

}

Answer 1

In main function we are doing nothing but calling another function f().So time complexity of main function is as same as time complexity of function f(),therefore we only need to compute the time complexity of function f().

void f(int n) {

int i = 1; // Declaring and initialising integer variable i = 1 ( SUPPOSE IT TAKES (a) UNIT OF TIME )

while (i <= sqrt(n)) { // This while loop runs sqrt(n) times  

if (n % i == 0 ) { // Suppose checking if() condition takes (b) UNIT OF TIME

printf("%d, %d\n", i, (n / i)); // Suppose printing statement takes (c) UNIT OF TIME

}

i += 1; // This equation is as same as (i = i + 1) of suppose adding 1 to i that is ( i + 1 ) takes (d) UNIT OF TIME and then assigning i + 1 to i ( i = i + 1) takes (e) UNIT OF TIME

}

So while loop takes (b+c+d+e)√n UNIT OF TIME

}

int main() {

f(36); // Calling Function f()

}

TIME COMPLEXITY OF FUNCTION f() :-

=> a + (b+c+d+e)√n ( COMPLEXITY IN TERM OF CONSTANT (a,b,c,d,e) ) .

TIME COMPLEXITY IN big-O NOTATION IS :-

=> O(√n ) .