For each of the following code fragments give running time a

For each of the following code fragments give running time analysis (Big Oh) a. sum =0; for (i=0; i

Solution

Answer:

a) Here is a for loop which runs from i = 0 to n , thus total running time = n = O(n)

b) Here are two loops , first loop running from i = 0 to n and second loop running from j = 0 to i which itself running till n. Hence total time = n*n = n^2 = O(n^2).

c) Here are 3 loops

Hence total time = n*n^2*n^2 = n^5 = O(n^5)