Analyze the time complexity of the following functions or fo

Analyze the time complexity of the following functions or for-loops. For each question, use the following template to figure out the total time needed to finish the corresponding function or for-loop. double sum_skip 10 (double array[], int n) double sum_exponentials(int n)//n is a power of 3. i.e.. n=3^k or k=log_3n {int sum=0; for (int i=1; i

Solution

1) sum=0 - 1 time - 1 unit

i=0 - 1 time - 1 unit

i<n - n/10 times or units

i=i+10 - n/10times or units

sum=sum+array[i] - n/10 times or units

Total = 3n/10 +2= O(n)
2)
sum=0 - 1 time - 1 unit

i=0 - 1 time - 1 unit

i<n - n/3 times or units

i=i*3 - n/3times or units

sum=sum+i - n/3 times or units

Total = 3n/3+2= n+2= O(n)
3)

i=0 - 1 time - 1 unit

i<n - n times or units

i=i++ - n times or units

In the inner loop j=n runs for n time units max
j>=i runs for n*n time units when i=0
Similarly j++ also runs for n*n times
Total = 2n^2 +3n+1= O(n^2)
4)
for-i runs for m time units
i=0 1time
i<m m times
i++ - m times
for-j runs for m*p time units
j=0 m times
j<p m*p times max
j++ m*p times
for-k runs for m*p*n time units
Same applies to k=0 -m*p times

k<n and k++
Addition inside runs for m*p*n time units

Total time = 3(m*n*p)+3(m*p)+3m + 1=O(mnp)