0
$\begingroup$

is the Big-O for this O(1) or some asymptotic like 1/n?

Saying that because if it defaults, the time limits at about 1000000 ns, but if it returns while in the loop, it is about a fraction of that. The time seems to increase very slightly as the inputs increase.

public static int[] call(int b, int c) {
    int[] f = new int[2];
    final double n = 1.13;

    for (int x = -100; x < 100; x++) {
        for (int y = -100; y < 100; y++) {
            if (((n+x)*(n+y)) == ((n*n)+(b*n)+c)) {
                f[0] = x;
                f[1] = y;
                return f;
            }
        }
    }
    return f;

    /* // timer method
     * long startTime = System.nanoTime() ;
     * call();
     * long endTime   = System.nanoTime() ;
     * long totalTime = endTime - startTime;
     * System.out.println(totalTime);
     * 
     *      f(2, 1)   : 499284
     *      f(4, 4)   : 487452
     *      f(6, 9)   : 501479
     *      f(8, 7)   : 493296 
     *      f(10, 21) : 500602
     *      f(12, 36) : 505862
     *      
     */

}

Also, please ignore that the code is wonky.

|cite|improve this question
$\endgroup$
1
$\begingroup$

The upper bound doesn't get affected by inputs b & c so we can say it is $O(1)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Even though the time increases with inputs? Edit: Never mind, I misunderstood. Thank you! $\endgroup$ – Peaser Feb 20 '17 at 5:44
  • $\begingroup$ That is because of early exit from the loop but while calculating upper bound consider the worst case. $\endgroup$ – Deep Joshi Feb 20 '17 at 5:47

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.