This week's 📊biweₑakly quiz will be very short, more of a hook than a quiz. A 2-parter, on two different things! #weaeklyquiz

First one: Fibonacci. Recall that the Fibonacci numbers are defined recursively by F₀=F₁=1, and 𝐹ₙ₊₂=𝐹ₙ₊₁+𝐹ₙ
for n≥0.

Now, you can generalize that a little by changing the initial conditions...

1/

... and consider the task of computing, given as input two initial values F₀, F₁, and an integer n, the value 𝐹ₙ.

Q1: How hard is it? Assuming that addition and multiplication of arbitrary numbers takes time O(1), what is the running time of the best algo to solve the above task?

2/

Exponential in n 🥥
9.7%
Quadratic in n 🧁
3.2%
Linear/near-linear in n 🍪
22.6%
Sublinear in n🍦
64.5%
Poll ended at .
@ccanonne what is a "number"? Integers? Floats? Arbitrary rings?
@olligobber Your pick. I didn't want to get into bit complexity and the computational complexity of multiplying integers or reals.
@ccanonne Yay, I pick matrices!

@olligobber oh come on... Fair, I should have replied more carefully.

(That'd be the same answer even with multiplication of reals, incidentally)