CODEWITHSUNDEEP
algorithmperformancebig-ocomplexity-theory
John
John

Reputation: 1

Big-O notation of an algorithm that runs max(n,0) times?

I have the following algorithm:

for(int i = 1; i < n; i++)
    for(int j = 0; j < i; j++)
        if(j % i == 0) System.out.println(i + " " + j);

This will run max(n,0) times.

Would the Big-O notation be O(n)? If not, what is it and why?

Thank you.

Upvotes: 0

Views: 70

Answers (2)

Mo B.
Mo B.

Reputation: 5827

You haven't stated what you are trying to measure with the Big-O notation. Let's assume it's time complexity. Next we have to define what the dependent variable is against which you want to measure the complexity. A reasonable choice here is the absolute value of n (as opposed to the bit-length), since you are dealing with fixed-length ints and not arbitrary-length integers.

You are right that the println is executed O(n) times, but that's counting how often a certain line is hit, it's not measuring time complexity.

It's easy to see that the if statement is hit O(n^2) times, so we have already established that the time complexity is bounded from below by Omega(n^2). As a commenter has already noted, the if-condition is only true for j=0, so I suspect that you actually meant to write i % j instead of j % i? This matters because the time complexity of the println(i + " " + j)-statement is certainly not O(1), but O(log n) (you can't possibly print x characters in less than x steps), so at first sight there is a possibility that the overall complexity is strictly worse than O(n^2).

Assuming that you meant to write i % j we could make the simplifying assumption that the condition is always true, in which case we would obtain the upper bound O(n^2 log n), which is strictly worse than O(n^2)!

However, noting that the number of divisors of n is bounded by O(Sqrt(n)), we actually have O(n^2 + n*Sqrt(n)*log(n)). But since O(Sqrt(n) * log(n)) < O(n), this amounts to O(n^2).

You can dig deeper into number theory to find tighter bounds on the number of divisors, but that doesn't make a difference since the n^2 stays the dominating factor.

So the tightest upper bound is indeed O(n^2), but it's not as obvious as it seems at first sight.

Upvotes: 2

ADdV
ADdV

Reputation: 1252

max(n,0) would indeed be O(n). However, your algorithm is in O(n**2). Your first loop goes n times, and the second loop goes i times which is on average n/2. That makes O(n**2 / 2) = O(n**2). However, unlike the runtime of the algorithm, the amount of times println is reached is in O(n), as this happens exactly n times.

So, the answer depends on what exactly you want to measure.

Upvotes: 1

Related Questions