Heh - I forgot the trick where if you set a default value in the function signature, the instance persists.

Thanks for the pointer

How big are the numbers you are testing locally? In the tests inputs go up to 1000. When I run your memoized function (after manually increasing the recursion limit), it takes a good 20 seconds or so. You need a better algorithm (Hint: memoize results between function calls too, not just for a single function call)

Note: Using Python

Testing my algorithm offline, I can complete a 100000 test run in 1.15 seconds. In the codewars environment, this times out after 12 seconds, meaning that I cannot submit my solution.

Annoying...

:-)))

I've tested your solution and it passes at 7 seconds interval whilst mine passes at around 1.5 seconds. Not a kata issue, closing...

No, the 2nd sentence implies that recursion is not needed since we have stored the pre-computed result in a specific data structure, and we only need to fetch that data from it upon needing it.

Also, your solution should be using memoization O(1) complexity instead of O(N)

If you write that solution without looking back at the code from the external links, then it is not. Happy coding ! ^^

Your solution has O(N) time complexity. Memoization technique requires O(1) to pass the test.

OP solved it in a quite unique way, closing ^^.

OP solved it, closing.

OP is now a Code-golfer in Python, closing ^^

Memoization / look-up approach is required. The expected time complexity is O(1).

OP solved it, closing

5 years later, CW WIKI has been deprecated, and now we have community-based documented guidelines. A lot is still in progress but it is definitely more comprehensive than the former. Have a good read if you manage to see this message someday when notification gets fixed ! ^^

Sorry if it is a duplicate of what others have already said but it seems that the tests are not independent from the performance point of view. I mean results must be memorized not only within a single calculation but must be shared between two different calls of the function:

fib(100) -- takes some time to give the answer
fib(50) -- takes (approximately) no time as it is calculated already during the previous call