0

According to the topic, fibonacci complexity formula is 1.6180339887^N.

Expected complexity is F(20) =1.6180339887^20=15126.99992456369

I have following test:

@Test
public void fibonacciTest() {
    AtomicInteger counter = new AtomicInteger();
    System.out.println("Fib number=" + fib(20, counter));
    System.out.println("Complexity=" + counter.intValue());
}


private int fib(int index, AtomicInteger counter) {
    counter.incrementAndGet();
    if (index <= 1) {
        return index;
    }
    return fib(index - 1, counter) + fib(index - 2, counter);
}

The output is:

Fib number=6765 Complexity=21891

Question:

Why the output differ from expected complexity?

Maksym
  • 4,434
  • 4
  • 27
  • 46
  • Why do you use atomic type for the counter? – Yola Apr 11 '18 at 10:04
  • Primitives as well as wrappers are immutable in Java. AtomicInteger is mutable. – Maksym Apr 11 '18 at 10:06
  • Ah, i see, i'm a C++ programmer, so didn't know this. But that is hard to believe that having local/member variable, you can't change its value:( – Yola Apr 11 '18 at 10:27
  • In addition to Yola's answer it might be good to know that (1.618..)^n is the tight bound for the complexity of the function. – swit Apr 11 '18 at 10:36
  • I would agree, but the way they calculate that number is pretty clear and complexity should be pretty much precise. – Maksym Apr 11 '18 at 11:23
  • Sorry, what do you mean precise? In the answer you linked it is `~θ(1.6^n)` which isn't precise. That's really `F(n)` or `F(n)*2-1` depending on how you count it. – Yola Apr 11 '18 at 11:31
  • https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/ – Maksym Apr 11 '18 at 11:38
  • That is exactly the same that i'm telling you. `T(n) = O(1.6180)^n`, so that's not exact value. See two lines above, they drop lower order terms, Big-O allows it. – Yola Apr 11 '18 at 11:55
  • They dropped really small part. The formula is T(n) = O(((1+$\sqrt{5})/2)^n+((1-\sqrt{5})/2)^n), so in our case we would get 15127 instead of 15126.9999 – Maksym Apr 11 '18 at 13:08
  • 2
    The "complexity" (big-O notation) only specifies the behavior *up to* a multiplicative constant, so you shouldn't expect the values to be equal to each other. Also, 15126.9999 is partly due to floating point imprecision and partly because your base 1.6180333... is not the precise value of the golden ratio. – meowgoesthedog Apr 11 '18 at 17:18
  • In general yes, but in our case big-O calculation is pure mathematical formula, so we should get correct number. – Maksym Apr 12 '18 at 10:30
  • 1
    Sorry, what do you mean pure mathematical formula? There are constant factor and lower order terms hidden in big-O notation, they influence the number we get. – Yola Apr 13 '18 at 05:04
  • 1
    It is not the *correct* (exact) formula though, so you should not expect identical values regardless. And your terminology "pure mathematical formula" makes no sense. – meowgoesthedog Apr 13 '18 at 14:31
  • I would like to get correct mathematical formula, how can I get it? Code is simple, so it's possible mathematically calculate exact number of operations. – Maksym Apr 13 '18 at 15:10

1 Answers1

1

The difference is because there is no Fibonacci number with value 0. The numbers starts with 1, 1, 2, 3, 5. Your function returns index which could be zero.

private int fib(int index, AtomicInteger counter) {
    counter.incrementAndGet();
    if (index <= 2) {
        return 1;
    }
    return fib(index - 1, counter) + fib(index - 2, counter);
}

With this setup you will get 6765*2-1 which is kinda about θ(1.6^n) as the answer you mention states. It doesn't mean that complexity equals to 1.6^n exactly.

The formula is enter image description here. You can see as n grows, second term becomes negligible.

EDIT:

I would like to get correct mathematical formula, how can I get it? Code is simple, so it's possible mathematically calculate exact number of operations.

To answer this question we need to count number of all nodes in the tree, as you increment counter in every node.

enter image description here

#1 + #2 = #2 + #3 = (#3 + #4) + #3 = #3 + #4 + (#4 + #5) = #3 + #4 + #5 + (#5 + #6) = ...

So, #1 + #2 equals to number of all internal nodes plus one. The plus one comes from the fact that we will count root node twice, ... #N + (#N + 0). But, also, #1 + #2 equals to Nth Fibonacci number. So, the formula you requested is:

#op = 2 * fib(N) - 1
Yola
  • 18,496
  • 11
  • 65
  • 106