Time Complexity/big o notation for nested loop recursion

Question

I am looking at the following code

public class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            for (long b = 0; b * b <= c; b++) {
                if (a * a + b * b == c)
                    return true;
            }
        }
        return false;
    }
}

the author is stating the time complexity for this code is √c. What i don't understand is how.

So suppose we are giving an example of c=20. then the code will run 15 times however √20=4.47

What is the question you have? And can you link to the original assignment/homework/article? — Progman
– Progman, Commented Jan 25, 2020 at 11:54
Seems like the code should be close to o(n) in complexity by a taking a quick glance at it. Running sqrt(n) in the outer loop and about sqrt(n) /2 in the inner one — DJSchaffner
– DJSchaffner, Commented Jan 25, 2020 at 12:09
This is linear, not √. I believe it's √ in the best-case scenario, but it's not the same thing — Fureeish
– Fureeish, Commented Jan 25, 2020 at 12:09
@dev_ios999 The article says it's O(c), so why do you said it's O(sqrt(c))? — Progman
– Progman, Commented Jan 25, 2020 at 12:29

Julian Durchholz · Accepted Answer · 2020-01-25 13:22:31Z

8

The given snippet is O(n) and Ω(√n), implying the stated time complexity is merely best case.

*Logarithmized vertical axis

answered Jan 25, 2020 at 13:22

Julian Durchholz

4404 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Scratte · Accepted Answer · 2020-01-25 16:30:49Z

I just wanted to see some actual runs. √c seems to be the best case scenario. I suspect that happens when a = 0 and b * b = c, eliminating the need for multiple runs of the outer loop.

prints:
  i =           10      sqrt =      3   runs =            8
  i =          100      sqrt =     10   runs =           11
  i =        1,000      sqrt =     31   runs =          351
  i =       10,000      sqrt =    100   runs =          101
  i =      100,000      sqrt =    316   runs =        4,121
  i =      500,000      sqrt =    707   runs =       71,501
  i =    1,000,000      sqrt =  1,000   runs =        1,001
  i =    5,000,000      sqrt =  2,236   runs =      521,209
  i =   10,000,000      sqrt =  3,162   runs =      382,721
  i =   50,000,000      sqrt =  7,071   runs =    7,079,001
  i =  100,000,000      sqrt = 10,000   runs =       10,001

Printed with:

public class StackOverflowTest {
  static int counter;

  public static void main(String[] args) {
    print(10);
    print(100);
    print(1000);
    print(10000);
    print(100000);
    print(500000);
    print(1000000);
    print(5000000);
    print(10000000);
    print(50000000);
    print(100000000);
  }

  static void print(int i) {
    new Solution().judgeSquareSum(i);
    String format = "  i = %,12d\tsqrt = %,6d\truns = %,12d\n";
    System.out.printf(format,i,(int)Math.sqrt(i),counter);

  }

  static class Solution { // only added a counter
      public boolean judgeSquareSum(int c) {
          counter = 0;
          for (long a = 0; a * a <= c; a++) {
              for (long b = 0; b * b <= c; b++) {
                  counter++;
                  if (a * a + b * b == c)
                      return true;
              }
          }
          return false;
      }
  }
}

Dave The Dane · Accepted Answer · 2020-01-25 14:50:25Z

Put another way: if a² + b² = c, the limiting case is:

a² + 0² = c (& of course 0² + b² = c, which is analagous)
-> a² = c
-> a = √c

So, for any b, a <= √c

The originally posted code checks a * a <= c for every iteration.
It is considered best practice (because its faster) to evaluate limiting values once only.
As we just saw, a * a <= c can be rewritten as a <= √c

So the for-loop could be coded as follows:

final long rootC = (long) Math.sqrt(c);

for (long a = 0; a <= rootC; a++) {
    :
    :
}

...which I hope makes the √c complexity claim for the original code clear.

The 2nd for-loop is unnecessary, as b can be calculated empirically

For any a:
a² + b² = c (where c is known)
-> b² = c - a²
-> b = √(c - a²)
(only integer values of b being acceptable)

Dave The Dane · Accepted Answer · 2020-01-25 14:53:22Z

-1

This can be further optimised to:

public boolean judgeSquareSum(final int c) {

    final long rootC = (long) Math.sqrt(c);

    if (c == rootC * rootC) {
        return true;
    }

    for (long a = 0; a <= rootC; a++) {

        final long aSquared = a * a;
        final long b        = (long) Math.sqrt(c - aSquared);

        if (aSquared + b * b == c) {
            return true;
        }
    }
    return false;
}

The above produces identical results to the original Posting for all +ve c.

edited Jan 25, 2020 at 14:53

answered Jan 25, 2020 at 12:54

Dave The Dane

9611 gold badge9 silver badges24 bronze badges

1 Comment

Andreas Over a year ago

That is Approach 3 in the leetcode article

Dave The Dane · Accepted Answer · 2020-01-25 12:43:52Z

-5

Your Max conditions are

a * a <= c

and

b * b <= c

If you take the Square Root of both sides you get a <= √c & b <= √c

So, if you optimise your code for performance...
(i.e. don't calculate the maximum on every iteration!)
...it would look like this:

public boolean judgeSquareSum(final int c) {

    final long rootC = (long) Math.sqrt(c);

    for (    long a = 0; a <= rootC; a++) {
        for (long b = 0; b <= rootC; b++) {

            if (a * a + b * b == c) {
                return true;
            }
        }
    }
    return false;
}

So now you see where the complexity claim of √c came from.

edited Jan 25, 2020 at 12:43

answered Jan 25, 2020 at 12:32

Dave The Dane

9611 gold badge9 silver badges24 bronze badges

6 Comments

Scratte Over a year ago

But wouldn't that make it rootC * rootC = c?

Andreas Over a year ago

With nested loops, you multiply the complexities of each loop. O(√c) * O(√c) = O(√c * √c) = O((√c)²) = O(c)

Dave The Dane Over a year ago

Scratte & Andreas are obviously not Mathematicians. If a * a <= c, then √a <= c for all a >= 0.

Scratte Over a year ago

Lets assume that the loops were both < n. That would make the complexity n * n = n², right?

Andreas Over a year ago

@DaveTheDane "If a * a <= c, then √a <= c for all a >= 0" Yes, since √a <= a * a for any integer value a, but what does that have to do with anything? Outer loop is O(√c). Inner loop is O(√c) by itself, so inner loop inside outer loop is O(√c * √c) = O(c). I'm not a pro mathematician, but I do know basic Big-O math like that.

|

Collectives™ on Stack Overflow

Time Complexity/big o notation for nested loop recursion

5 Answers 5

Comments

Comments

Comments

1 Comment

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related