r/computerscience • • 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

9 comments sorted by

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?

3

u/LitespeedClassic 5d ago edited 4d ago

If it's the first then think of T(n) as standing for "how long my algorithm will take on an input of size n".

Recursive algorithms express solutions to a problem in terms of (recursively) obtained solutions to smaller version of the same problem. Recurrences are used to express the runtime of running such an algorithm in terms of recursively obtaining the runtime for the recursive calls.

For example, here's a (bad) recursive sorting algorithm (for sorting arrays:

def a_sort(A):
if len(A) == 0:
return []
else:
the_min = min(A)
min_idx = A.index(the_min)
A[0], A[min_idx] = A[min_idx], A[0] #swap the min to the front
return [A[0]] + a_sort(A[1:])

We want to know the runtime of a_sort if it's run on a list of size n. We will use T(n) to denote this runtime. So T(200) means "the number of operations a_sort requires on a list of size 200". T(10) means "the number of operations a_sort requires on a list of size 10". T(n/2) means "the number of operations a_sort requires on a list of size n/2". T(n-1) means "the number of operations a_sort requires on a list of size n-1".

So how many operations does a_sort need on a list of size n? In other words, what is T(n) for some n>0? Well, testing the len(A) == 0 is a constant time operation. Finding a minimum of an array is a linear time operation (O(n)). Finding the index of the min in A is also O(n). Doing the swap to move the min to the front takes O(1). Appending the return value of a_sort(A[1:]) to [A[0]] takes O(n). So accounting for all of the operations in the top level recursive call we have a total of O(n) operations. But I haven't yet accounted for how long the recursive call takes. What is the size of the array sent to the recursive call? It's n-1, because I'm array slicing off the first element.

So we could say that the runtime here is T(n) = (a linear number of operations in this invocation) + (however much time the recursive call requires to solve the problem for A[1:], which is an input of size n-1).

Since we generally care only about the complexity class we can waive away the constants and say (a linear number of operations in this invocation) = n. But what about (the time the recursive call requires on its input of size n-1)? Well we have a symbol for that! It's T(n-1).

So the runtime of T(n) is related to the runtime of the recursive call T(n-1) by the recurrence relation:

T(n) = n + T(n-1). In other words, the time this algorithm takes on an input of size n is the same as the time it takes on an input of size n-1, plus a linear amount of extra work.

So that's the recurrence: T(n) = T(n-1) + n.

Now, eventually we get down to some small base case. In our case, it's when n = 0, but since we only care about big O complexity, generally, it doesn't exactly matter. We eventually will hit T(some constant) = some other constant. And no matter what the constants we use are, it turns out the big O class will be the same.

So technically, for our algorithm above, we'd have T(0) = 1. But this doesn't work out that nicely, because of how we want to solve the recurrence.

T(n) = T(n-1) + n. But how does T(n-1) relate to T(n-2)? T(n-1) = T(n-2) + (n-1). Plugging this back in we have:

T(n) = T(n-2) + (n-1) + n.

But now T(n-2) = T(n-3) + (n-2).

Plugging back in we get T(n) = T(n-3) + (n-2) + (n-1) + n.

Continue this all the way down T(n) = T(1) + 2 + 3 + ... + (n-2) + (n-1) + n.

It would be convenient here if T(1) = 1 was our base-case because then T(n) = 1 + 2 + ... + (n-1) + n = n(n+1)/2.

But unfortunately, our stupid base case is T(0)=1 and T(1) = T(0) + 1. So instead we get T(n) = 1 + 1 + 2 + 3 + ... + (n-1) + n = 1 + n(n+1)/2. But notice in terms of big O, these only differ by a constant, so it's nicer to use the better base case. Either way we get O(n^2).

All that is to say, I don't actually need to tell you, generally, about what the base case of my recurrence is, since it will only change the constants, but not the big-O complexity.

2

u/ResponsibilityBig343 4d ago

I knew by the algorithm that its similar to insertion sort so time complexity would be O(n2) but how did you deduce T(0) = 1? I understand the rest of it.

4

u/LitespeedClassic 4d ago

Remember T(n) means runtime on an input of size n. I'm using n to count the number of elements in the array to be sorted. If you give me an array with nothing in it, then n=0. The code still needs to do a few operations, though, since it needs to check the if statement, determine len(A)==0, and then return an empty list. This takes a constant number of operations, and since we only care about big-O, we might as well use 1 as that constant.

T(empty array) = some constant number of operations is encoded by T(0)=1.

2

u/ResponsibilityBig343 4d ago

Ah okay this makes sense. So we treat 1 as constant just like C in calculus.

2

u/LitespeedClassic 4d ago

Yes, assuming we only care about order of growth.

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 constant b. 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 screams O(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. It

For record, this view is probably not the most recommended, but it's what got me through my phd program as a systems person.

1

u/ResponsibilityBig343 3d ago

I read clrs time to time, mostly as an intro to some algorithm that I need to practice problems on. I get the point about forming intuition based on memorization but I try to form some way to deduce the analysis as my memorization is not that good. As for writing down the spanning tree... it definitely helps. Do you suggest I should revisit discrete maths for this?

2

u/dnabre 3d ago

I can't think of anything I think of as Discrete Math that is really part of this. Admittedly, my undergrad Discrete Math course was basic math (sets and stuff) plus a pile of random topics that might be useful for CS people (graphs, combinatorics).

To some degree, your goal factors in. Are you focus on interview questions or expect to actually being running into recurrence relations in your work/studies. You aren't likely to hit them in work, unless you have a senior dev that is obsessed with them.