Important Note: This is NOT Big O notation Im trying to figure out Time Complexi
ID: 3570752 • Letter: I
Question
Important Note: This is NOT Big O notation
Im trying to figure out Time Complexity, yet all the recources online don't clearly how to arrive that the total time. So here are questions with answers (assumingly correct, some might have errors). I need someone to explain clearly so i can understand how one arrived at the answer. And the last question is on recursion, find the time for the base case and recursive case, explain how you got there thanks.
Q1.
double sum_fifth (double array[], int n)
//n: size of the array. Assume n is divisible by 5
{
double sum=0; //1
for (int i=0; i//1 + n/5
sum = sum + array[ i ]; //n/5
return sum; //1
}
Q2.
double sum_exponentials(int n)
//n is a power of 10, i.e., n=10k or k=log10n
{
int sum=0; //1
for (int i=1; i//log10n + 1
sum = sum + i; //log10n
for (j=0; j< n; j++) // (log10n) * (n+1)
sum = sum + j; // (log10n) * n
}
return sum; //1
}
Q3.
for (int i=n; i>=0; i--) //n + 2
for (int j=i; j// (n+2)(n+1)/2
cout << i <<
Explanation / Answer
1. O(n)
because the loop runs n times from 0 to n-1 ...so n-1 steps are needed
2. O(n^2)
a loop inside a loop ...so
for inner loop it's O(n) and now for outer loop it becomes sum of O(i) for all i from 1 to n-1
so it's O(n^2)
3.
O(n)
here also second loop has j increasing and first loop has i decreasing ....and both the loop runs n+1 times...
so unlike the last one it's in linear time. remember that the for loop doesnt have braces for it's scope so the loops are two different ones here.
if braces were there then it will be O(n^2) as inner loop and outer loop both runs n+2 times.
4.
here it's the same as the 3rd question ..the time complexity remains same i:e if braces are there then it's O(n^2) and if braces are not there it's O(n).
remember that here the inner loops runs only for n/2 +1 times ...but still the time complexities remain the same.
Optional answers :::
1.
O(n^2) if braces are there.... and O(n) if braces are not there for the for loop...
here j runs different times than i just like in question 4
2.
here also the complexities remain same as optinal question 1 but the i loop runs different number of times and so does the j .
4.