It's a huge meme among the high school students attending LUISS lessons about competitive programming, each year the "know it all" ends up saying "I can get fib(N) in almost O(1)"
Can't get over the fact that the "God-Tier" Programmer is concerned about time & space complexity and speed and then chooses to use Python of all languages lol
For the Fibonacci sequence, if you just need a specific number of it, you can use matrix exponentiation and calculated really large indices very quickly
@@kjl3080 idk what that is. I solved it by manually deriving an f(2n) and f(2n-1) function in terms of f(n) and f(n-1) then just cached the immediate previous states. This resulted in O(log(n)) time and O(1) space. code: " def fib(self, n: int) -> int: f0 , f1, r0, r1, i = 1, 1, 0, 1, 1 while i
@@padraighill4558 x^2-x-1 *nerd* tho u dont even need generating functions or characteristics polynomials, because Q(sqrt(5)) is kinda intuitive due to similarity with complex numbers. Or just use matrices, it works just the same. But its better to use polynomials division for longer linear recurrences, cuz O(k^2logn) is better than O(k^3logn). I just like the idea of using Q(sqrt(5)), it can mathematically prove some very fun properties
While I agree that storing the entire array is not needed for a single call to this function, if we make the array static (reusable between function calls), we effectively get a cache. At any point, if we have solved the problem up to size M and n M, we just append to our cache until we solve for n, making n the new largest solved problem. Assuming that the inputs follow some reasonable probability distribution without too heavy of a tail and are uncorrelated, then the runtime should converge to an average of O(1).
It's funny that my uni professor solved the fib question with recursion and I solved it with iteration on the test and I got a 0 for it. I talked with him, googled in the front of him to prove that it can be solved with a loop to get my marks on test.
Any recursive problem can be solved with a loop, this is programming 101 and does not need proving. Some problems are just more suited for recursive solutions. Maybe the requirement was to use a recursive approach?
I hope you enjoyed the video, thanks for watching! The sentiment behind this one is that many people I tutor (email greg.hogg1@outlook.com if you're interested) get stuck in a "let's just solve it and not worry about speed" way of thinking. This is okay to start, but I think you should always learn the best approach (and even some of the worse but different approaches) to solving each problem. In this one I show that Leetcode will actually accept your O(2^n) recursive backtracking solution, even though an O(n) approach exists as well. Drop a like and subscribe if you found this helpful!
I know a general formula of fibonacci by solving its difference eqns but from what I understand, it is not computationally viable because the sqrt(5)'s will accumulate floating point errors.
I would just write absolutely garbage and slow code but write it in a language like c++ or rust so it's fast. This may mean i am a noob programmer but i digress
Why can't you solve this in O(1)? It's possible, you "just" find the closest integer (round half up) where F(n) = phi^n / sqrt(5) where phi is the golden ratio [1+sqrt(5)]/2. You can grab the 1 billionth Fibonacci number if your language's number representation can handle arbitrarily large numbers.
I find your videos are a great way to learn and look at other ways to program fascinating. I have been a back office developer for over 3 decades building business systems. This was the way I was taught the fit the industries in the Midwest and East Coast. I have never had to use DSA in my systems in the way you are showing. A lot of the tools and operating systems I worked with handled most of this for you. Now that bI’m on the West Coast, I have to get past the culture shock and learn DSA. The problem I have is, once I picked up a lot of this knowledge, I never use it in my daily work. That’s when I forget it all.
Yeah that's pretty common. People generally learn this stuff well when they need it for interviews, and start to forget about it on the job. That's natural and okay. And thank you for the kind words :)
@@Ibra_ There is. You learn it in Linear Algebra courses in colleges. Actually any linear recursive defined function like fibonacci has general solution.
Nice, meme. But for anyone serious about this. Part 1 was the god-tier programmer. Part 2 was the noob one.. It's called premature optimization, which is pointing and wrangling with stuff that just works fine. Programmers go from bad, to worse, to good. The good ones know to appreciate working code and some level of readability. Anything else usually just burns money.
Having that said! Being able to go from recursive to iterative is very useful. It doesn't take too much to buffer overflow. Just don't default to it. Default to simple and readable. It's an optimization. Always start with simple and readable. Always, always.. it works, it works... If you for some reason cannot understand that.. We must be on different planets.
@@g3mint446 This is not premature optimization, the quote is always misinterpreted when it's actually intended to talk about micro-optimizations. Here, the algorithm is changed to a more efficient one. Also, since we're talking about readability, I'd say the second algorithm is much more readable considering it's much closer to what an human would actually do to manually calculate the Fibonacci sequence instead of the recursive solution. Finally, saying the first solution "just works fine" is wrong in my opinion considering it runs in non-polynomial times when there exists many simple polynomial time solutions and the non-polynomial time solution is unable to be used in a real world context considering it gets so slow it can't calculate numbers past like 60-70 in a reasonable amount of time.
@@anto_fire8534 I have to agree with you there. But only if your team think it's the most readable and simple way to write code. If you don't have a clear need to rewrite readable code, why would you? I can do a million things to improve something, it doesn't mean I should. You get the most value from code that is readable, maintainable and working (not some smart ass genious, waste of time code). Some times you don't even need to read it again, it should just work. It is all about time management, and there are cases where scrapping the thing and making it just work is preferable to anything else. Anyone who call themselves an expert but cannot realize this, is not an expert (those people are lying to themselves). I have worked with horrible code and great code. I very much value simple code, but some times the code doesn't matter enough to be a priority, the project is, not the code. The project and the solution spec is the priority. That is what the Manager and the Customer has agreed on, and that is what they need you to help them with. Not a single thing beyond. If you have suggestions to do more, it should be clearly reported and discussed. That is my obligation as a developer. That is my job. Itching my brain and having arrogant opinions is not. I get work done fast and as ordered, that is my job. That is how I keep customers and managers happy. Not by being a genious. Your job is not your company, you don't decide how to run it.
You can get the 2n-th and 2n+1-th fibonacci number if you have the n-th and n+1-th. If you consider multiplication to be constant, this is actually an O(log(n)) solution.
Here is the more or less standard way to solve it: def fib(end): last = 0 current = 1 for i in range(end): yield current current, last = current + last, current This gives you a generator that builds it while going along without storing it as necessary. Alternatively you can build in the option for infiite generation, but you often do not want that.
@GregHogg Actually if you write tail recursive functions you will get the same time and space complexity :) Stack recursive functions are bad of course
Wait why I feel like I'm learning wrong way I did exactly what is best and then I was taught to do recursion 😮 that's not right it's like the simpler the better
This is decent for most real world applications but an O(n) algorithm is too lame to be called god tier imo. Use matrix exponentiation and we have O(logn).
@@warguy6474 might be less accuracy due to the 64 bit double/integer precision limit in most of the languages but it will be much faster than the O(n) approach in any given input size.
The God tier would use Matrix based calculation for logarithmic space and time for the most optimal solution... My disappointment is immeasurable and my day is ruined.
God tier would use math and linear algebra to prove there is a general formula to calculate the nth number in the fibonnacci suite (it's called Binet's formula) and then the algorithm is in time complexity of 0(1)
You are a junior programmer... the problem is not the recursion. The problem is the way you wrote that recursive program, that calculate many times the sames numbers. You can make the program recursive without doing that. You wrote an O(2^n) solution when you can make an O(n) one.
@@GregHogg easy. a number is A number. (for example: 3 or 28 or 137) a secuence is COUNTLESS numbers that are in a certain, relevant, order. (for example: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ... or 1, 3, 5, 7, 9, 11, 13, 15, 17 or 2, 3, 5, 7, 11, ...)
God tier wouldn't store the whole array which makes it O(n) space complexity. Instead only store previous two for O(1) space.
Exactly my first though
Technically, god-tier would use matrix exponentiation to get it in O(log n) time and O(1) space.
Absolutely correct:)
Is that really god tier? I'm a first year cs student and thought of that. Kinda feels like the most intuitive way to do it imo.
@@rikthecuber can you explain? Never heard of it
Mathematician: "Well, I'll just use the Binet's Formula."
It's a huge meme among the high school students attending LUISS lessons about competitive programming, each year the "know it all" ends up saying "I can get fib(N) in almost O(1)"
that still needs loops for the pow
I thought about it too 😮
@@mattiamarchese6316it's closer to log n tho due to it being the fastest you can get the exponent
Exactly what I was thinking
Only 2 variables are needed. Overkill for using array😅
Yep, you're right!
Even then, if you're going to use an array, at least preallocate it.
Technically 3 for a swap, no?
@@joshnjoshgaming you can also use the xor operator to swap two numbers without having to introduce another variable. will use more cycles, though
@@joshnjoshgaming There's a "slightly" more elegant way for using 2 variables only. It's a bit useless memory-wise tbh, but good for thinking.
Can't get over the fact that the "God-Tier" Programmer is concerned about time & space complexity and speed and then chooses to use Python of all languages lol
God tier python programmer I suppose 😂
At least it isn’t Java or JavaScript
@@_Epidemic_ still faster than python most of the time but yeah, I'd have expected like c++
Just for fibonacci ?? Why not use a memoized recusive function and reduse speed from exponential to linear🤔🤔🤔
@@808brotherstv4 think he does that in another video actually. though it wouldn't surprise me if that was also in python.
For the Fibonacci sequence, if you just need a specific number of it, you can use matrix exponentiation and calculated really large indices very quickly
Yes absolutely right
is there a word in english for the god above god?
@@MengdaYang Yes, Computer Science Major :P
"god-tier" then proceeds to store a big list. And in python. Lol
@GregHogg You can also represent linear sequence with a matrix and use fast exponantiation to get O(logn) time complexity with O(1) space complexity
Binet Eigenvalues my beloved
@@kjl3080 idk what that is. I solved it by manually deriving an f(2n) and f(2n-1) function in terms of f(n) and f(n-1) then just cached the immediate previous states. This resulted in O(log(n)) time and O(1) space.
code:
"
def fib(self, n: int) -> int:
f0 , f1, r0, r1, i = 1, 1, 0, 1, 1
while i
The most optimal is literally just using the formula: (((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)
"I use Binet's formula, btw"
Loses precision for big n
@@gabrielushijima1525do calculations in Q(√5)
@@aertyty3900 Just Q[x] / (x^2 + x - 1)
@@padraighill4558 x^2-x-1 *nerd*
tho u dont even need generating functions or characteristics polynomials, because Q(sqrt(5)) is kinda intuitive due to similarity with complex numbers. Or just use matrices, it works just the same. But its better to use polynomials division for longer linear recurrences, cuz O(k^2logn) is better than O(k^3logn). I just like the idea of using Q(sqrt(5)), it can mathematically prove some very fun properties
While I agree that storing the entire array is not needed for a single call to this function, if we make the array static (reusable between function calls), we effectively get a cache. At any point, if we have solved the problem up to size M and n M, we just append to our cache until we solve for n, making n the new largest solved problem. Assuming that the inputs follow some reasonable probability distribution without too heavy of a tail and are uncorrelated, then the runtime should converge to an average of O(1).
It's funny that my uni professor solved the fib question with recursion and I solved it with iteration on the test and I got a 0 for it.
I talked with him, googled in the front of him to prove that it can be solved with a loop to get my marks on test.
Any recursive problem can be solved with a loop, this is programming 101 and does not need proving. Some problems are just more suited for recursive solutions.
Maybe the requirement was to use a recursive approach?
Considering it's uni, the test probably meant to test certain subject and not so much on the result
Ask your professor if his implementation can do fib(100),
Spoiler: it can't, unless it doing some internal cache
Wow that's brutal
First year programming is learning how to use recursion, second year programming is learning never to use recursion.
This is solvable in closed form…
Dynamic programming 101.
But, you could also use some kind of queue etc to store only last two elements :).
I am to lazy for variables :)
You're right!
I hope you enjoyed the video, thanks for watching! The sentiment behind this one is that many people I tutor (email greg.hogg1@outlook.com if you're interested) get stuck in a "let's just solve it and not worry about speed" way of thinking. This is okay to start, but I think you should always learn the best approach (and even some of the worse but different approaches) to solving each problem. In this one I show that Leetcode will actually accept your O(2^n) recursive backtracking solution, even though an O(n) approach exists as well. Drop a like and subscribe if you found this helpful!
Oh i just did this. You're supposed to use the power of matrix (1,1;1,0)
FINALLY someone who know how to efficiently calculate Fibonacci sequence.
You can use general formula for Fibonacci numbers with complex numbers to get even faster solution
sure as long you can provide a valid proof in the interview I would accept it
I know a general formula of fibonacci by solving its difference eqns but from what I understand, it is not computationally viable because the sqrt(5)'s will accumulate floating point errors.
@@rikthecuber you can just round numbers because you know they are int
@@fastneuro9829Maybe we could use Newton's Method to approximate the square root? And then round in the end?
@@tomasbernardo5972 probably yes
u can literally solve that in O(log(n)) using maths
how?
Using fast matrix exponentation
@@igorkaminski6543 and what's that? Could you please elaborate more?
Or cleverly manipulating thr Catalan identity
I would just write absolutely garbage and slow code but write it in a language like c++ or rust so it's fast. This may mean i am a noob programmer but i digress
Lmao yeah that works
Slow code is by definition still slow in "fast" languages
Why can't you solve this in O(1)? It's possible, you "just" find the closest integer (round half up) where F(n) = phi^n / sqrt(5) where phi is the golden ratio [1+sqrt(5)]/2.
You can grab the 1 billionth Fibonacci number if your language's number representation can handle arbitrarily large numbers.
You're right!
Exponential is not constant time
Nvm I can’t read
C’s ** algo is most certainly log(exponent)
I find your videos are a great way to learn and look at other ways to program fascinating. I have been a back office developer for over 3 decades building business systems. This was the way I was taught the fit the industries in the Midwest and East Coast. I have never had to use DSA in my systems in the way you are showing. A lot of the tools and operating systems I worked with handled most of this for you. Now that bI’m on the West Coast, I have to get past the culture shock and learn DSA. The problem I have is, once I picked up a lot of this knowledge, I never use it in my daily work. That’s when I forget it all.
Yeah that's pretty common. People generally learn this stuff well when they need it for interviews, and start to forget about it on the job. That's natural and okay. And thank you for the kind words :)
watched this a few times and it still breaks my head
you are absolute god expect you are appending all the useless values to list, instead of using using 2 variables
it's dp
When I see problems like these I tend to just solve it mathematically and throw in the general solution to get a O(1) space and about O(1) time code
But there is no mathematical equation that can just get you the fibonacci number without knowing the 2 before
@@Ibra_ Binet's formula:
@@Ibra_ There is. You learn it in Linear Algebra courses in colleges. Actually any linear recursive defined function like fibonacci has general solution.
I feel stupid for not knowing that. Thank you guys
The thing is, we are taught the second method first as kids and then later the recursive method, as a cooler way to solve the problem.
You can also use dynamic programming with the recursive solution for the same time complexity
Yep!
You can also implement the fibonacci function for O(1)
There's no backtracking in the recursive solution
Yeah that's kinda true. Moreso just naiive recursive solution
The way that I learned is to use "memoization" technique + recursive, and I thought that this was the best way to do this lol!!!
Nice, meme. But for anyone serious about this. Part 1 was the god-tier programmer. Part 2 was the noob one.. It's called premature optimization, which is pointing and wrangling with stuff that just works fine. Programmers go from bad, to worse, to good. The good ones know to appreciate working code and some level of readability. Anything else usually just burns money.
Having that said! Being able to go from recursive to iterative is very useful. It doesn't take too much to buffer overflow. Just don't default to it. Default to simple and readable.
It's an optimization. Always start with simple and readable. Always, always.. it works, it works... If you for some reason cannot understand that.. We must be on different planets.
This is not premature optimization.
@@anto_fire8534 I don't agree, good code is relative to needs and goals. Maybe you have an argument in there?
@@g3mint446 This is not premature optimization, the quote is always misinterpreted when it's actually intended to talk about micro-optimizations. Here, the algorithm is changed to a more efficient one. Also, since we're talking about readability, I'd say the second algorithm is much more readable considering it's much closer to what an human would actually do to manually calculate the Fibonacci sequence instead of the recursive solution. Finally, saying the first solution "just works fine" is wrong in my opinion considering it runs in non-polynomial times when there exists many simple polynomial time solutions and the non-polynomial time solution is unable to be used in a real world context considering it gets so slow it can't calculate numbers past like 60-70 in a reasonable amount of time.
@@anto_fire8534 I have to agree with you there. But only if your team think it's the most readable and simple way to write code. If you don't have a clear need to rewrite readable code, why would you? I can do a million things to improve something, it doesn't mean I should. You get the most value from code that is readable, maintainable and working (not some smart ass genious, waste of time code).
Some times you don't even need to read it again, it should just work. It is all about time management, and there are cases where scrapping the thing and making it just work is preferable to anything else. Anyone who call themselves an expert but cannot realize this, is not an expert (those people are lying to themselves).
I have worked with horrible code and great code. I very much value simple code, but some times the code doesn't matter enough to be a priority, the project is, not the code.
The project and the solution spec is the priority. That is what the Manager and the Customer has agreed on, and that is what they need you to help them with. Not a single thing beyond. If you have suggestions to do more, it should be clearly reported and discussed. That is my obligation as a developer. That is my job. Itching my brain and having arrogant opinions is not.
I get work done fast and as ordered, that is my job. That is how I keep customers and managers happy. Not by being a genious. Your job is not your company, you don't decide how to run it.
I am sitting here glad the "God tier" solution was easy
That's awesome!
You can get the 2n-th and 2n+1-th fibonacci number if you have the n-th and n+1-th. If you consider multiplication to be constant, this is actually an O(log(n)) solution.
using matrices you can achieve asymptotics O(log n)
Yes!
Here is the more or less standard way to solve it:
def fib(end):
last = 0
current = 1
for i in range(end):
yield current
current, last = current + last, current
This gives you a generator that builds it while going along without storing it as necessary. Alternatively you can build in the option for infiite generation, but you often do not want that.
Are people actually jumping straight to recursions without thinking about other ways of solving issues?
Absolute god who doesn’t care about O(N) space and time taken for appending to list not to mention recreating if hit upper limit. 😂
Could go for a Fibonacci matrix exponentiation, though you would get overflow, but you'll want to calculate large Fibonacci numbers modulo some number
(The recursive algorithm is not a backtracking algorithm)
Yeah I think I misspoke
Legends use matrix exponentiating
How is that constant time? When looping through n 🙄
"this is slow"
proceeds to use arrays in python
lol
I was fully expecting "Pro Tier" where you just call a library function.
And people who know math would do it in constant time and space complexity.
May I know what sote is it?
Or you could just use something really cool called Binet's formula
Meanwhile me who can do it O(1) time
How?
@@gvenkatesh8935 There's a closed form solution. Search for Binet's forumula
@@gvenkatesh8935JonBristow posted it below, there's a formula for calculating the nth fib number which is constant time.
@@mtheos What is fun you can derive a comparable formula for any recursively defined sequence
@GregHogg Actually if you write tail recursive functions you will get the same time and space complexity :) Stack recursive functions are bad of course
Excellent point!
Those who don't know backtracking are real noobs😂😂
Two variables can do the job
Indeed they can!
I don't know how does it happens on your language, but in my language adding new element into dynamic array - it is very expensive operation.
can you give me the links of these questions? that i try to solve them myself
and the memory?
what if i want to learn most of god tier methods , how do i search and learn !?
Wait why I feel like I'm learning wrong way I did exactly what is best and then I was taught to do recursion 😮 that's not right it's like the simpler the better
no, recursion is good. That program is badly done
I have no idea what any of this means but I’m looking forward to failing to ever truly understand what any of this means.
God tier would use binary matrix exponentiation to get the answer in O(log n)
And then theres Titan God tier programmer: use an api thats optimized for you.
This is decent for most real world applications but an O(n) algorithm is too lame to be called god tier imo. Use matrix exponentiation and we have O(logn).
Haha yep you've got a point
where is he solving this question on?
I like your funny words, magic man.
Hehe
>noob programmer
>Recursion
Yeah, that's a good joke
a=0
b=1
For(int i=2;i
whats the extension in VS Code that measures the performance?
This is leetcode
Legend programmer with a Degree from Havard :
Math.round(1/(5**0.5) * (1+(5**0.5))/2)**(n)
With just a logn approach 🗿🗿
exactly...
ok but you lose accuracy and speed for really large inputs
@@warguy6474 true, there is a better formula that you can use
@@warguy6474 might be less accuracy due to the 64 bit double/integer precision limit in most of the languages but it will be much faster than the O(n) approach in any given input size.
@@paulkanja is it?? could you tell me??
Memoization anyone?
Oh yeah
Use this instead of the array
a, b = 0, 1
For _ in range(n):
Print(a)
a, b = b, a + b
Tried DP yet ?
Honestly, both solutions are subpar. Or maybe it was intended as satire, I don't even know anymore.
Somewhat satire, moreso entertaining helpful. Yes there's even more optimal solutions
Dynamic Programming 😍
Then I'm a non-existent programmer because I don't know either solution haha
Binet's formul does it in O(1) time and space
If you really cared about speed, you wouldn't be using Python
Or, we could overkill and do this in O(log n) time for the fancy points.
True God tier: mathematician using o(1) binets formula
God tier whould use formula to calculate final value
you just need 2 numbers why store all?
both forgot to name the class and method names correctly - the code wouldn't get discovered or used
The God tier would use Matrix based calculation for logarithmic space and time for the most optimal solution... My disappointment is immeasurable and my day is ruined.
God tier would use math and linear algebra to prove there is a general formula to calculate the nth number in the fibonnacci suite (it's called Binet's formula) and then the algorithm is in time complexity of 0(1)
😂 super mega nerdy coder tier
You can just calculate it using a formula for constant time. Sometimes doing it the better algorithmically way fails if you don't know the math.
You can do even faster using matrices
He said recursive and I shuddered
Lolll
Im an idiot in programming and I still wouldn’t do recursive backtracking lol
So not an idiot!
use the general form of the sequence would be even faster
I'm a beginner. What website it this? Just curious, thx
Leetcode
This is how I program. If it works, it works.
How about using a generating function and then it's o(1)?
That's not how it works
Use the (φ^n - (1-φ)^n)/√5 technique
You are a junior programmer... the problem is not the recursion. The problem is the way you wrote that recursive program, that calculate many times the sames numbers. You can make the program recursive without doing that. You wrote an O(2^n) solution when you can make an O(n) one.
Yes we cache it and make it o(n)
You could've kept the recursive approach and added caching, and you will get the same results as the tabular dynamic programming.
Not quite the same results as for loops are better than recursion. But you're right, same time complexity
It's not a god tier programmer, he just wasted sh*tload of memory instead of solving it in constant space.
matrix exponentiation is best solution for general Fibonacci problem
You're right
Fibonacci of -n is (-1)^(n + 1) fib(n)
If you're just starting out, what language would you guys advise learning first?
JavaScript or Python. Personally if i were to go back I would choose js, it's just more practical
@GregHogg practical in what sense? Is it a more in-demand language from employers?
You can reduce the space complexity to O(1) bro, why didn't you
broo wtf?!!! you look like my bro James more than my bro James looks like himself
Step aside, peasants.
n = int(input("how many Fibonacci numbers do you want?"))
x,y = 1,1
for i in range(1, n+1):
print(x)
x,y = y, x+y
god tier matematician.
there's no fibonacci NUMBER.
closest you could get to "fibonacci number" would be "the numberS on the fibonacci SEQUENCE".
Not sure why there's a distinction lol
@@GregHogg easy.
a number is A number. (for example: 3 or 28 or 137)
a secuence is COUNTLESS numbers that are in a certain, relevant, order. (for example: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ... or 1, 3, 5, 7, 9, 11, 13, 15, 17 or 2, 3, 5, 7, 11, ...)
Bruh I literally wrote the same program for fibonacci number while learning C++ because I hadn't learnt recursion.
Nice!
The god program is actually the noob at this point. Who thinks of recitation as a first option
You can do it in logarithmic time ))
Im god tier then
Yeah you are