determine the frequency count Determine the frequency counts

Determine the frequency counts for all statements in the following two pro- gram segments:

Solution

Answer:

a) For the statements , there are three for loops. Now first loop running from 1 to n ---- > O(n)

Second loop running from j to i ( which inturn running from i to n ) -------------------------> O(n)

Third for loop running from k to j ( which in turn running from j to i and i itself running from i to n ) ----> O(n)

Take the product = O(n) x O(n) x O(n) = O(n^3)

b) This while loop running from i to n , so the complexity is O(n).