1

i have following code:

for ( int i = 1; i < n; i ++)
    for ( int j = 0; j < n*n; j ++)
        if (j % i == 0)
           for (int k = 0; k < j; k++)
               sum++;

How would if (j % i == 0) affect the overall complexity? As k goes up to j, which is n*n, the third loop should also be of complexity n*n= O(n^2), am i right? So it would be O(N)*(N^2)*(N^2)= O(n^5)? But the solution given is O(n^4), so where am i wrong? Thanks!

I'm familiar with the basic concepts of BigOh, but i'm not understanding this specific case, as my calculations for the sum of the nested loops (with the first one repeating the second one n times and the second one repeating the third one n^2 times and the third one being n^2 also would sum up to n^5) differs from what i know it is (n^4). So it has to be something about if (j % i == 0) that reduces the exponent by one. As j is in average way bigger than i, there should be a good possibility that if (j % i == 0) is fulfilled. But why does it decrease the overall complexity's exponent exactly by one ? I have searched Google at SE but i didn't find any infos on a modulo integrated into a nested loop like this. Thanks in advance.

  • 2
    Possible duplicate of What is O(...) and how do I calculate it? – gnat Mar 29 '16 at 16:35
  • @gnat: The answer at that post is essentially link-only. Is that supposed to be a canonical post? It doesn't succeed in that regard. – Robert Harvey Mar 29 '16 at 17:44
  • @RobertHarvey did you check the note at the end of it? "this question is a canonical dupe target" etc – gnat Mar 29 '16 at 18:56
2

Given a loop

for i from 0 to n exclusive:
  if i is divisible by a:
    f(i)

we can see that f(i) will be executed n/a times (to be precise: 1 + floor((n-1)/a) for n > 0 times). The running time for this subexpression would then be T(n) = ∑i=0...(n-1)/a F(a·i). In your specific case, my a is not a constant, and will therefore cancel out one n.

  • You'd need to be a bit careful if n is smaller than a (for example if n = 1000, and you check divisibility by 1 million, the "if" is true once, not 0.001 times), but in this case i ≤ n, while j goes up to n^2. – gnasher729 Mar 30 '16 at 0:05
0

This isn't actually an answer to your exact question; more like an alternative way of going at things. If you don't need a theoretically sound answer and simply want to know whether your code will perform well enough for larger input sizes, there's a simple way to determine the answer to questions like that empirically. Especially if you can't figure out the theoretical bounds and you already have the basic code structure in place.

Add a counter variable to the innermost loop. Basically, you already have one (sum). Run your code for a few different sizes of n, say for n=100, 1000, 1e4, 1e5, 1e6 etc and look at how your counter grows. Use finer-grained steps if the running time for larger values of n grows prohibitive. You can graph the resulting data using a spreadsheet and get an idea as to how similar the graph looks to standard time complexity functions.

When your loops and branching logic get more complicated, often that's the quickest way to get some insight into how your code will actually behave. If you add two counters, one inside the branch and one outside, you can also get a feeling for how many times the branch is not taken.

This also helps to validate answers you arrive at by reasoning about time complexity in a more formal manner.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.