CODEWITHSUNDEEP
algorithmbig-o
doctopus
doctopus

Reputation: 5647

What is the big-O of this program where nested loops depend on each other?

Can't figure out what the big O for this block of code is. Outer loop is log(n), but how bout inner loop that depends on outer loop?

for (int i = 1; i < A.length; i = i * 3) {
    for (int j = i; j < A.length; j++) {
        // Simple computation
    }
}

Any help greatly appreciated :)

Upvotes: 0

Views: 140

Answers (2)

OmG
OmG

Reputation: 18838

If A.Length == n, the inner loop runs in n-i each time. Hence, the total complextiy of the program is sum(n - i) for i = 1, 3, 9, ..., n = 3^log_3(n). As the number of i is log_3(n), the complexity is T(n) = n * log_3(n) - (3^(log_3(n)+1)-1) = n * log_3(n) - 3(n-1) = O(nlog(n))

Upvotes: 1

redmoncoreyl
redmoncoreyl

Reputation: 197

As is your code will not complete because i = i * 3 means that i will always be 0.

From your comment it is supposed to be i = 1. So, on each iteration of the outer loop, the problem size is reduced by a constant factor of 3. This means that the outer loop takes O(log n) steps.

The inner loop takes O(n) in the worst case and is run O(log n) times. Therefore, the entire running time is O(n log n).

Be sure to check your post for typos and do some research in the future :).

Upvotes: 1

Related Questions