Analyze the time complexity of the following functions or for-loops. You are req
ID: 653217 • Letter: A
Question
Analyze the time complexity of the following functions or for-loops. You are required to demonstrate the main steps.
Q1.
double sum_skip7 (double array[], int n)
//n: size of the array. Assume n is divisible by 7
{
double sum=0;
for (int i=0; i<n; i=i+7)
sum = sum + array[ i ];
return sum;
}
Q2.
double sum_exponentials(int n)
//n is a power of 5, i.e., n=5k or k=log5n
{
int sum=0;
for (int i=1; i<n; i=i*5)
sum = sum + i;
return sum;
}
Q3.
for (int i=0; i<100; i=i+2)
for (int j=0; j<n; j++)
cout << i <<
Explanation / Answer
1.
for any value of n, the loop runs for n/7 times. So, the complexity is O(n/7) = O(n)
2.
for any value of n, the loop runs for log n times(base of log = 5). So, complexity is O(log n)(base of log = 5)
3.
The outer loop runs for 100 / 2( = 50) times. For each time the outer loop runs, the inner loop runs for n times. So, the complexity is: O(50 * n) = O(n)
4.
The outer loop runs for n times. For each time the outer loop runs, the inner loop runs for (n + 1) times.
So, complexity = O(n(n + 1)) = O(n^2 + n) times = O(n^2).
5.
The outer loop runs for m times. For each time the outer loop runs, the middle loop runs for p times.
for each time the middle loop runs, the inner loop runs for n times. So, complexity = O(m * p * n)