Write Tn for the following algorithm Explain how you calcula

Write T(n) for the following algorithm. Explain how you calculated it. Indicate whether the fragment execution time is O(n) or O(n^2): for (int i = 0; i = i; j--) cout

Solution

If n =3

When i = 0 , inner loop runs from j=n-1 to i times i.e. 3 times

When i=1 , inner loop runs for j=n-1 to i times i.e n-1 = 2 times

When i=2 , inner loop runs for j=n-1 to i times i.e n-2 = 1 times

So total no of times of execution = 3 + 2 + 1= 6 times when n= 3

If n=4 , total no of execution = 4 + 3 + 2 +1 = 10 times

So the formula here is = n(n+1)/2 i.e. sum of all numbers upto n

T(n) = (n^2 + n)/2

Hence execution time is O(n^2)