For each of the following Program fragments give an analysis

For each of the following Program fragments, give an analysis of the running time (Big Oh answer will do). sum = 0; for (i = 0; i

Solution

A) As we can see,

for (i=0 ; i < n; ++i ) ----------------------->Runs n+1 times [n times when i<n and once when i=n , so n+1 time]
     ++sum; ----------------------->Runs n times [Because the for loop condition is satisfied n times]

So Overall Time Complexity is n+1 + n = 2n+1 = O(n)

B) for (i=0 ; i < n; ++i ) ----------------------->Runs n+1 times [n times when i<n and once when i=n , so n+1 time]
              for (j=0 ; j< n; ++j ) -------------->Runs n(n+1) times [n times because of outer for loop and n+1 time itself]
    ++sum;->Runs n*n times [n times because of outer for loop and n time itself n because of inner for loop

So overall Time complexity is n² + n(n+1) + n = O(n² )


C) B) for (i=0 ; i < n; ++i ) ----------------------->Runs n+1 times [n times when i<n and once when i=n , so n+1 time]
              for (j=0 ; j< n; ++j ) -------------->Runs n(n+1) times [n times because of outer for loop and n+1 time itself]
                           for (k=0 ; k< n; ++k ) ---->Runs n²(n+1) times [n² times because of outer for loops and n+1 time itself]
                                       ++sum;->Runs n*n*n times [n*n*n because of three loops ]


So overall Time complexity is n³ + n²(n+1) + n(n+1) + n = O(n³)



Thanks, let me know if there is any doubt/clarification required.