4 ms·

One thing this reminds me of is the use of "Compute the nth Fibonacci number" as an interview question. The interviewer may expect you to show off your knowledg

by fogof 5y ago

One thing this reminds me of is the use of "Compute the nth Fibonacci number" as an interview question. The interviewer may expect you to show off your knowledge of dynamic programming by memoizing the function. But you take a risk if you implement the matrix exponentiation algorithm [1], which is actually optimal in that it only uses O(log(n)) arithmetic operations. I had an interviewer once who seemed a bit skeptical when I mentioned there was a sublinear algorithm for Fibonacci. [1] : https://math.stackexchange.com/a/867404/165144 https://math.stackexchange.com/a/867404/165144

bialpio 5y ago
Is it really sublinear though? The data that the algorithm accepts is a number n, the size of the data is thus m=log(n), so the algorithm runs in O(m) time -> linear in terms of data size. I vaguely recall there was some nuisance related to this (pseudopolynomial algorithms ring a bell), but haven't interviewed in a while so may be misremembering it.
- Jtsummers 5y ago
  It is sublinear, n is the nth Fibonacci number, or the size of the series up to the desired value. The standard (non-naive) algorithm is linear with respect to n. The matrix version makes use of fast exponentiation which is log(n), using the same n as before the target Fibonacci number.
  - bialpio 5y ago
    log(n) is ok. Sublinear with respect to n is also ok. "Sublinear" on its own is not, at least if my understanding is correct (sublinear relative to what?), although I can see that it can be a common shortcut to make.
    - Jtsummers 5y ago
      All the necessary information to answer your question is in the original comment. They're talking about computing the nth Fibonacci number and say that the matrix exponentiation version is O(log(n)). Unless you think they're using n to represent two (potentially) different things, there is little room for confusion. "sublinear" refers back to that O(log(n)) algorithm.
      - bialpio 5y ago
        They are representing n to mean 2 different things. In this case, n is meant to represent a value passed in to the algorithm. The problem is that complexity is usually expressed relative to size of the input, which in case of this algorithm is log(n) = m bits. This makes the exponentiation version actually linear in terms of bits needed to represent the input. It's like saying that an algorithm that accepts n x n matrix and takes O(n) steps to compute something is "linear" - it's not linear, because the size of the data is m = n^2, which makes it O(sqrt(m)).
        Jtsummers 5y ago
        What two things do they use it to mean? There's literally only one thing it refers to in the original comment: The nth Fibonacci number. Show me the second. All additional uses of n in that comment are references to that same thing, the nth Fibonacci number.
        bialpio 5y ago
        In our case n = value of the input, log(n) = size of the input. Complexity is expressed relative to the size of the input. Size of the input is also usually expressed as n, which is shadowed by "value of the input" in the problem statement, so "sublinear with respect to n" has different meaning than "sublinear with respect to size of the input", & saying "sublinear" when talking about complexity implicitly translates into "sublinear with respect to the size of the input", which is incorrect without any additional statements - exponentiation algorithm is "linear with respect to the size of the input".
        Jtsummers 5y ago
        Asymptotic analysis is about finding some quantifiable property (or properties) of an algorithm (in this case it can be seen as the index into the sequence of Fibonacci numbers) and determining how fast the algorithm "grows" (in this case it's about time, not space, though can be used for space as well) with respect to that quantifiable property. The original commenter uses n to indicate which value in the sequence is being computed. They then say that there is a O(log(n)) algorithm (that is, it grows with the logarithm of the index) that can find the nth Fibonacci number. The n in O(log(n)) is still referring to that same index in the sequence, it has not changed its meaning. I do not know how else to explain this to you. At this point I can only presume that you are confused about the fundamentals of algorithm analysis or you're a troll.
- ball_of_lint 5y ago
  If you're computing the time complexity this way, then the simple linear dynamic programming is actually quadratic, and the matrix exponentiation algorithm is still faster. Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. That might be less appropriate for fibonacci than most other problems though.
  - bialpio 5y ago
    > Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. I think this assumption can still be taken for the exponentiation version - I'm more nitpicking about the fact that there is a simple way to rephrase the problem (see below) to arrive at a different meaning of "linear" vs "sublinear" and it's better to be very explicit in cases where things may be misunderstood. Rephrasing: fib(x) takes an x which is an array of bits of length m, which are the binary representation of number n. Return nth Fibonacci number.
AlexanderTheGr8 5y ago
Technically, you can calculate the nth Fibonacci number in O(1) with the golden number.
- Jtsummers 5y ago
  It's still O(n) or O(log(n)) as you have to compute the value using exponentiation to the nth power. Which offers either a linear algorithm or a faster logarithmic algorithm if you use fast exponentiation. It isn't actually O(1).

by fogof 5y ago

bialpio 5y ago

Is it really sublinear though? The data that the algorithm accepts is a number n, the size of the data is thus m=log(n), so the algorithm runs in O(m) time -> linear in terms of data size. I vaguely recall there was some nuisance related to this (pseudopolynomial algorithms ring a bell), but haven't interviewed in a while so may be misremembering it.

Jtsummers 5y ago
It is sublinear, n is the nth Fibonacci number, or the size of the series up to the desired value. The standard (non-naive) algorithm is linear with respect to n. The matrix version makes use of fast exponentiation which is log(n), using the same n as before the target Fibonacci number.
- bialpio 5y ago
  log(n) is ok. Sublinear with respect to n is also ok. "Sublinear" on its own is not, at least if my understanding is correct (sublinear relative to what?), although I can see that it can be a common shortcut to make.
  - Jtsummers 5y ago
    All the necessary information to answer your question is in the original comment. They're talking about computing the nth Fibonacci number and say that the matrix exponentiation version is O(log(n)). Unless you think they're using n to represent two (potentially) different things, there is little room for confusion. "sublinear" refers back to that O(log(n)) algorithm.
    - bialpio 5y ago
      They are representing n to mean 2 different things. In this case, n is meant to represent a value passed in to the algorithm. The problem is that complexity is usually expressed relative to size of the input, which in case of this algorithm is log(n) = m bits. This makes the exponentiation version actually linear in terms of bits needed to represent the input. It's like saying that an algorithm that accepts n x n matrix and takes O(n) steps to compute something is "linear" - it's not linear, because the size of the data is m = n^2, which makes it O(sqrt(m)).
      - Jtsummers 5y ago
        What two things do they use it to mean? There's literally only one thing it refers to in the original comment: The nth Fibonacci number. Show me the second. All additional uses of n in that comment are references to that same thing, the nth Fibonacci number.
        bialpio 5y ago
        In our case n = value of the input, log(n) = size of the input. Complexity is expressed relative to the size of the input. Size of the input is also usually expressed as n, which is shadowed by "value of the input" in the problem statement, so "sublinear with respect to n" has different meaning than "sublinear with respect to size of the input", & saying "sublinear" when talking about complexity implicitly translates into "sublinear with respect to the size of the input", which is incorrect without any additional statements - exponentiation algorithm is "linear with respect to the size of the input".
        Jtsummers 5y ago
        Asymptotic analysis is about finding some quantifiable property (or properties) of an algorithm (in this case it can be seen as the index into the sequence of Fibonacci numbers) and determining how fast the algorithm "grows" (in this case it's about time, not space, though can be used for space as well) with respect to that quantifiable property. The original commenter uses n to indicate which value in the sequence is being computed. They then say that there is a O(log(n)) algorithm (that is, it grows with the logarithm of the index) that can find the nth Fibonacci number. The n in O(log(n)) is still referring to that same index in the sequence, it has not changed its meaning. I do not know how else to explain this to you. At this point I can only presume that you are confused about the fundamentals of algorithm analysis or you're a troll.
ball_of_lint 5y ago
If you're computing the time complexity this way, then the simple linear dynamic programming is actually quadratic, and the matrix exponentiation algorithm is still faster. Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. That might be less appropriate for fibonacci than most other problems though.
- bialpio 5y ago
  > Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. I think this assumption can still be taken for the exponentiation version - I'm more nitpicking about the fact that there is a simple way to rephrase the problem (see below) to arrive at a different meaning of "linear" vs "sublinear" and it's better to be very explicit in cases where things may be misunderstood. Rephrasing: fib(x) takes an x which is an array of bits of length m, which are the binary representation of number n. Return nth Fibonacci number.

AlexanderTheGr8 5y ago

Technically, you can calculate the nth Fibonacci number in O(1) with the golden number.

Jtsummers 5y ago
It's still O(n) or O(log(n)) as you have to compute the value using exponentiation to the nth power. Which offers either a linear algorithm or a faster logarithmic algorithm if you use fast exponentiation. It isn't actually O(1).