CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
Angelus
Angelus

Reputation: 105

Time Complexity of three nested for loops

There are three nested for loops, and I can find complexity if the loop increment by 1 but if the loop increment like this i+=c, I got confused?

    for (int i = 0; i < n; i+=c)
        for (int j = 0; j < i; j++)
             for (int k=0; k < m; k++)
                 result[i,j]= x[j]-y[k]

The complexity of the third for loop is m but for the first for loop I think is n/c and for the second for loop is n ==> multiply ranges together: n/c * n * m = n^2/c * m ==> the worst case is O(n^2). is this correct? How to find the total number of iterations using the sum form?

Upvotes: 0

Views: 372

Answers (1)

abc
abc

Reputation: 11929

The time complexity depends on two parameters in your case: m and n as the middle loop can be expressed as a function of the first.

If you consider the total number of iterations they are of the order of:

1/2 * m * n * (n-1) = O(mn^2)

The left part assumes c=1. However, given c as a constant the overall time complexity would not change.

If c is not given as a constant the resulting time complexity would be O(mn^2)/c

Upvotes: 1

Related Questions