There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
Agree with a comment or answer? Like () to up-vote the contribution!
It should be noted that the function outline it gives will actually retrieve the value at the index provided and not actually the Nth term in the sequence.
def fibonacci(n):
fibs = [0,1]
if n <= (len(fibs)-1):
return fibs[n]
else:
while n > (len(fibs)-1):
to_add = fibs[-1] + fibs[-2]
fibs.append(to_add)
return fibs[n]
Fibonacci numbers are a sequence, and in order to form a sequence we need a general term that defines each number in the sequence. Since the sequence is based upon addition, it follows we will have two sequential operands, the first being zero. This gives us a starting list, [0, 1]. If d is the difference between terms, this is the only time there is unity in a Fibonacci sequence. After that the ratio of any two latter terms begins to approach the Golden Ratio.
The fact that there is one instance where d is Unity is my argument for beginning the sequence with zero. Start with 1 and the next term as 1 then where is there any suggested sequence?
Yes, there are sequences, 1, 1, 2, 3, 5, … but the suggestive component is missing. The zero. Zero plus one is one.
I agree 100%, then as per your suggested sequence (which is what I also consider as fibonacci) 0, 1, 1, 2, 3, 5… the 4th element should be 2 not the 3rd (as given in the actual test case). Am I missing anything here?
We’re both in disagreement of the SCT, so I’d say, no, you’re not missing anything. Glean from this and move forward. Compromises are well and good part of the process.
I found this “Coding Throwdown” challenge lots of fun, but I’m curious about the run-times of the solutions we found. Am I missing something, or did we not get quizzed on those?
For example, here’s my solution (spoiler alert) to the Fibonacci challenge. I believe the run-time is O(N). Is that correct? Also, can you recommend a general strategy for testing function run-time?
def fibonacci(n):
base = {0: 0, 1: 1}
for i in range(2, n + 1):
base[i] = base[i-2] + base[i-1]
return base[n]
You are correct that the run time of each method (yours and mtf’s) is O(N). But that covers a lot of territory (i.e., 10 * O(N) is still O(N).). Also, besides run time, you need to consider memory. Your method involves creating a dictionary that contains every fib less than fib(n), whereas his keeps only two numbers in memory at a given time.
That said, why not actually measure the run times?. The module timeit is a great resource, very nicely explained here.
Using it to compare the two functions, we get:
Comparison of time (in seconds) taken
for each of two methods of computing fib(n),
1000 runs at each n.
n dict time tuple time
****************************
50 0.0164 0.0076
100 0.0360 0.0175
200 0.0726 0.0360
400 0.1604 0.0884
800 0.4011 0.2358
1600 1.0445 0.6996
3200 3.2599 2.2922
6400 11.0521 8.2141
>>>
(Source code here.)
You can see that for N < 1000 or so, doubling N does seem to more or less double the time. Also, the time for the “tuple” approach is consistently about one-half of the “dict” approach. These ratios begin to fall apart for higher N (fib(6400) has 1338 digits), presumably due to “real life” hardware considerations.
Your function uses fewer resources for the reasons Patrick mentions. I’d like to be writing more memory- and time- efficient functions, so I appreciate your sharing.
def fib(n):
if n < 0:
ValueError("Input 0 or greater only!")
fibs = [0, 1]
if n <= len(fibs) - 1:
return fibs[n]
while n > len(fibs) - 1:
fibs.append(fibs[-1] + fibs[-2])
return fibs[-1]
and I got myself wondering why would we need to declare the second if:
if n <= len(fibs) - 1:
return fibs[n]
instead of just using the last return outside the while loop to do a “return fib[n]”
since if the n is not greater than the len(fibs) it would just jump the loop like:
def fib2(n):
if n < 0:
ValueError("Input 0 or greater only!")
fibs = [0, 1]
while n > len(fibs) -1:
fibs.append(fibs[-1] + fibs[-2])
return fibs[n]
am I missing something or would my code actually make it cleaner?
Big-O is all about worst case and constants have no meaning in the analysis. It’s a ball park value. Based on that aim, we can simply say that each call happens twice for every value up to N which is where the 2^N comes from.
) below.
) to up-vote the contribution!