2
$\begingroup$

I have seen this function in past year exam paper.

public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

After give some example, I guess it is a function that with time complexity in following formula

let make m = n^(1/2)

[m+(m-1)+(m-2)+...+3+2+1] + [(m-1)+(m-2)+...+3+2+1] + ...... + (3+2+1) + (2+1) + 1

*Edit: I have asked this math question here, the answer is m(m+1)(m+2)/6

Is this correct, if no, what is wrong, if yes, how would you translate to big O notation. The question that I want to ask is not only about this specific example; but also how would you evaluate an algorithm, let's say, I can only give some example to watch the pattern it appears. But some algorithm are not that easy to evaluate, what is your way to evaluate using this example.

Edit: @LuchianGrigore @AleksG

public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

This is an example that in my lecture notes, each loop is with time complexity of n to the power of 1/2, for each loop there is another n^(1/2) inside, the total are n^(1/2) * n^(1/2) * n^(1/2) = n^(3/2). Is the first example the same? It is less than the second example, right?

Edit,Add:

How about this one? Is it log(n)*n^(1/2)*log(n^2)

for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)
$\endgroup$
  • 1
    $\begingroup$ What is the actual question here? Please restrict your self to one question. $\endgroup$ – Raphael Jun 19 '12 at 19:15
  • $\begingroup$ Each of the loops runs $\sqrt{n}$ times, for a total of $O(n^{3/2})$ $\endgroup$ – vonbrand Jul 25 '15 at 18:45
  • $\begingroup$ The last example is likely not doing what the thread starter thinks it does, and has complexity of O ((log n)^2). $\endgroup$ – gnasher729 Aug 29 '17 at 6:31
5
$\begingroup$

For one of the loops, you've a complexity of $O(\sqrt n)$. You're nesting the loops three times, so you'll get the complexity of $O(\sqrt n^3)$, which is $O(n^{3/2})$.

If you want to be more precise, then for your original question, the complexity will be:

  1. $O(\sqrt n)$ for the first loop
  2. $O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of 1 is constant.
  3. $O(\sqrt n - 2)$ for the third loop, which is the same as $O(\sqrt n)$, since the time complexity of 2 is constant.

Therefore, the total complexity is still $O(\sqrt n^3) = O(n^{3/2})$.

EDIT/ADD:

You're pretty much correct, just make one more step to simplify the expression, remembering that $\log(n^2) = 2 \times \log(n)$. There are three loops:

  1. The first on is, correctly, $O(\log n)$.
  2. The second one is just like in the first problem, so you get $O(\sqrt n)$.
  3. The third one is on the square of $n$, therefore you get $O(\log(n^2))$, which is the same as $O(2\log(n))$, which is the same as $O(\log(n))$.

Combining the three, it's pretty much like a multiplication, you will get: $O(\log(n) \times \sqrt n \times \log(n))$, which is $O(\log(n)^2 \times \sqrt n)$.

$\endgroup$
  • $\begingroup$ Edited, Sorry but I agree that first loop is O(n^(1/2)), but the 2nd & 3rd loop are not start from 1, but i & j. Is it still the same? $\endgroup$ – Timeless Jun 19 '12 at 8:37
  • $\begingroup$ @null Yes, you still will receive the same overall O-complexity. See my edit $\endgroup$ – Aleks G Jun 19 '12 at 8:47
  • $\begingroup$ @null The reason behind this is the following: Let's say we have only two nested loops. The inner loop starts at 1 for the first iteration of the outer loop, at 2 for the second iteration, ..., at sqrt(n) for the last iteration of the outer loop. So on average, it starts at around sqrt(n)/2 and ends at sqrt(n), which makes it O(sqrt(n)/2)=O(sqrt(n)) (the same as the outer loop). $\endgroup$ – brimborium Jun 19 '12 at 8:55
  • $\begingroup$ @AleksG since I have asked so many, would you mind to take a look at the added one, is it correct? $\endgroup$ – Timeless Jun 19 '12 at 9:54
  • $\begingroup$ @brimborium thanks, only care about the one with significant performance affect. so O(N^3+N^2+N) = O(N^3), right? Would you mind to take a look at the added example. Is my answer correct? $\endgroup$ – Timeless Jun 19 '12 at 9:56

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.