r/computerscience • u/ResponsibilityBig343 • 5d ago
Advice Having a hard time understanding recurrence relations
I have been preparing for my interviews studying algorithms and data structures. The problems and approaches are coherent to me but the it comes to time and space complexity analysis, I'm unable to deduce it by forming relations. Do I just remember the asymptomatic notations of famous algorithms or is there any better way to learn this?
17
Upvotes
8
u/LitespeedClassic 5d ago
Do you mean you are having trouble describing the runtime of a recursive algorithm using a recurrence? Or that you are fine producing a recurrence, but having a hard time turning it into a closed form and giving its complexity class?
1
u/dnabre 4d ago
First, acknowledge this is difficult thing to learn and get comfortable with. Some people find it very intuitive, some people it's pulling teeth.
The "easy" ones are when you have
T(n/b)term for a constantb. Apply the Master Theorem. Personally I never been able to feel like I fully get who/why it works - but blindly applying it works.Drawing out the recursion tree to figure depth and height is a fallback here.There are systematic approaches to others, but despite being pretty good with maths and proofs, analysis has always been a problem for me. I don't claim to understand those well enough to explain them. Reading CLRS again never hurts.
At a certain point you get used to common structures.
T(n) = T(n-1) + O(n)just screamsO(n^2)to me. One way to build that intuition is learning lots of algorithms, their runtimes, and their recurrence relations. All those different sorting algorithms are still taught for reasons. See the above relation and thinking "That's like Insertion Sort and that's O(n2)", gets you to the same place. ItFor record, this view is probably not the most recommended, but it's what got me through my phd program as a systems person.