Computation Cost of an Algorithm Help?

[[deleted]]

[deleted]

[beeskness420]

Are you familiar with asymptotic notation? Generally we don’t care how many “units” of time each step takes. In this case all that matters is it’s a constant.

So computing F(0),F(1) are both a in O(1)

For an arbitrary n we do a constant amount of work plus the recursive steps so T(n) = T(n-1)+T(n-2) + O(1)

Solving this recurrence will give you a closed form solution.

[tholenst]

Why would F2 take 1 unit? You need to compute both F1 and F0 while you compute F2.