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/
Second: complexity classes! P, PP, BPP, ZPP, are all actual #ComputationalComplexity classes. (I swear! It's true!)
Q2: Without looking it up, do you know how they relate to each other?
3/4
That's all. That's all for today! Longer quiz in ~2 weeks... in the meantime, answers and comments about this 2-parter in ≈3 days, as usual.
See you then!
PS: One of these two questions may be a (minor) trap.
4/end
Answers and discussion for last week's 📊biweₑakly quiz.
(For the quiz itself: https://mathstodon.xyz/@ccanonne/109842825668135282)
Only two questions — let's dive in, first with computing Fibonacci-type numbers!
How hard is it? I give you two initial values, and ask you to give me the n-th value of the sequence. Naively, implementing the recursion the "natural" way will give an exponential-time (in n) algo.
1/ #weaeklyquiz
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/
What's the issue? Look at the recursion tree! We keep recomputing everything many times: even Fib(n-2) is called twice, by Fib(n) and Fib(n-1). Not a great idea, let's say... 👀
2/
... but also very fixable. Don't keep recomputing the same values over and over again (which this code does during the recursion)! This gives the following (not elegantly written, but... that's just me) linear-time implementation. Phew! 😓
Linear time: O(n). Are we done?
3/
After all, O(n) is pretty good, right? Thing is: we can do better ✊. By avoiding a recursion entirely. Gosh, by avoiding to compute things (almost) entirely!
The key: F(n, F₀, F₁) is given by a linear recurrence relation, w/ constant coefficients: as such, one just solving the recursion explicitly, to get a closed form!
A closed form? Let's use it!
https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula
4/
@olligobber Yes -- you can keep all of it in the integer realm (until the last step, when you multiply a natrix with a vector containing F0 and F1). But given that for simplicity I assumed "all multiplications are free" I wanted to keep it simple in order not to dilute the main message:
"The fastest algorithm is the one you don't need to run."
Clément Canonne
olligobber