2 ms·
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 F
by 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 agoI 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.