Time complexity of the following C++ function(s) and/or for-loops. 1. double sum

ID: 3567198 • Letter: T

Question

Time complexity of the following C++ function(s) and/or for-loops.

1.
double sumit (double array[], int n)

//n: size of the array. Assume n is divisible by 5
{
double s = 0;

for (int a = 0; a < n; a = a + 5)

s = s + array[ a ];

return s ;

}

2.
double sum_exp(int n)

//n is a power of 10
{
int s = 0;

for (int a = 1; a < n; a = a * 10){

s = s + a;

for (b = 0; b < n; b++)

s = s + b;
}
return s;

}

The control of th program will enter inside the for loop (n / 5) times. So, the statement inside the for loop will execute n / 5 times.

So, complexity = O(n / 5) which will be written as O(n)

The outer loop will execute (log n) times, (base of log is 10, because everytime, i is multiplied by 10),

For each time in outer loop, the inner loop will execute n times.

So, the statement inside the inner for loop will execute (n * log n) times(base of log is 10).

So, complexity = n log n (base of log = 10)

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.