3 ms·

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 exp

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.
- bialpio 5y ago
  I really cannot make it clearer that I'm nitpicking on the statement that it is "sublinear". I'm not disagreeing that it's O(log(n)). I'm also not disagreeing that it's "sublinear with respect to n". I'm disagreeing with it being "sublinear", because there are at least 2 meanings that come to my mind: 1. "it's sublinear with respect to n" - this is true 2. "it's sublinear with respect to size of the input" - this is false I do not know how else to explain this to you that it is the size of the input that matters when talking about complexity. Example quora answer that recognizes the distinction (discussions about the technicality in the naive isPrime impl that checks numbers from 2 to sqrt(n)): https://qr.ae/pGuORe https://qr.ae/pGuORe.

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.

bialpio 5y ago
I really cannot make it clearer that I'm nitpicking on the statement that it is "sublinear". I'm not disagreeing that it's O(log(n)). I'm also not disagreeing that it's "sublinear with respect to n". I'm disagreeing with it being "sublinear", because there are at least 2 meanings that come to my mind: 1. "it's sublinear with respect to n" - this is true 2. "it's sublinear with respect to size of the input" - this is false I do not know how else to explain this to you that it is the size of the input that matters when talking about complexity. Example quora answer that recognizes the distinction (discussions about the technicality in the naive isPrime impl that checks numbers from 2 to sqrt(n)): https://qr.ae/pGuORe https://qr.ae/pGuORe.