0

I've been studying for interviews lately, and came across the computing of Fibonacci sequence question. I stumbled on this solution on the Wikipedia Rosetta page. They claim that it computes it in O(log (n)) time. However, wouldn't it be O(m(n)* log n ) where m(n) is the time for the multiplication of two numbers of n digits. I understand that it's O(log n ) arithmetic operations, but I don't believe it's also O( log n) time. Am I correct in this assumption or totally confused? Can someone clarify this for me?

Here's the code:

public class fibonacci {

public static long fib(long n) {
    if (n <= 0)
    return 0;

    long i = (int) (n - 1);
    long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2;

    while (i > 0) {
    if (i % 2 != 0) {
          tmp1 = d * b + c * a;
       tmp2 = d * (b + a) + c * b;
       a = tmp1;
       b = tmp2;
    }

        tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2));
        tmp2 = d * (2 * c + d);

        c = tmp1;
        d = tmp2;

        i = i / 2;
    }
    return a + b;
}   
}
B.oof
  • 1
  • I suspect that the multiplication of two numbers can be viewed as a constant, meaning that it stays O(log(n)). – Evan Knowles Sep 17 '14 at 06:33
  • 2
    possible duplicate of [What does O(log n) mean exactly?](http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly) – Nahuel Ianni Sep 17 '14 at 06:36
  • 1
    @NahuelIanni - you picked the right dup. :) – TheLostMind Sep 17 '14 at 06:37
  • Multiplication operations act on numbers with a finite representation (not depending on n), therefore an arithmetic operation in your case is constant time. – webuster Sep 17 '14 at 08:16
  • @EvanKnowles, webuser: But the representation of the n-th Fibonacci number has a length depending on n, especially exceeding all fixed-length formats. This argument is only valid for the computation of modular Fib numbers. – Lutz Lehmann Jan 31 '15 at 20:45
  • Overly correct, the length _fl_ of a positional representation of fib(_n_) cannot be bounded by a constant factor times that of _n_ (as with any superlinear function). Please argue _fl_ in O(_n_). – greybeard Jan 31 '15 at 20:55

1 Answers1

0

First there is an else missing the treatment of even and odd numbers. Second, it is not advisable (as in overkill) to use the power function to square a number.

But in total you are correct, if you use a variable digits library for big integers, then the cost for multidigit multiplication contributes essentially to the run time in the indicated form.

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51