this post was submitted on 26 Aug 2023
5 points (100.0% liked)
Programming Challenges
233 readers
1 users here now
Welcome to the programming.dev challenge community!
Three challenges will be posted every week to complete
- Tuesday (Easy)
- Thursday (Medium)
- Saturday (Hard)
Easy challenges will give 1 point, medium will give 2, and hard will give 3. If you have the fastest time or use the least amount of characters you will get a bonus point (in ties everyone gets the bonus point)
Exact duplicate solutions are not allowed and will not give you any points. Submissions on a challenge will be open for a week.
A leaderboard will be posted every month showing the top people for that month
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Without memoization, I believe the Fibonacci sequence is O(2^N). It's dependent on how long a sequence of digits is in the input, so your worst case is like O(2^N) if the string is mostly digits and best case being O(N) if there are only 1 or 2 digit sequences.
Someone can correct me if I'm wrong.
My implementation is memoized by
functools.cache
, but that is a concern when it comes to recursive Fibonacci. That, and stack overflows, which are also a problem for my code (but, again, not for "reasonable" inputs -- fibonacci(94) already exceeds 2^64).Time complexity-wise, I was more thinking about the case where the numbers get so big that addition, multiplication, etc. can no longer be modelled as taking constant time. Especially if
math.prod
andenumerate
are implemented in ways that are less efficient for huge integers (I haven't thoroughly checked, and I'm not planning to).That's pretty cool. I haven't dived too deep into python, so I should of looked up the library when you attached the
@cache
decorator. I learned something.