Running time using Big Θ notation

algorithm, analysis, python

Solution

`filter` has `n` recursive calls, but you also do a copy operation on each iteration which takes `n`, so you end up having Θ(n^2). If you implemented it 'properly' it should be Θ(n) though.

Same for `my_reverse`.

Same for `revfilter_beta`.

`revfilter_alpha` just does a `filter` and then a `reverse`, so thats Θ(n^2 + n^2) = Θ(n^2).

EDIT: Let's look into `filter` a bit more.

What you want to figure out is how many operations are performed relative to the size of the input. `O(n)` means that at the very worst case, you will do on the order of `n` operations. I say "on the order of" because you could, for example, do `O(n/2)` operations, or `O(4n)`, but the most important factor is `n`. That is, as `n` grows, the constant factor becomes less and less important, so we only look at the non-constant factor (`n` in this case).

So, how many operations does `filter` perform on a list of size `n`?

Let's take it from the bottom up. What if `n` is 0 - an empty list? Then it will just return an empty list. So let's say that's 1 operation.

What if `n` is 1? It will check whether `lst[0]` should be included - that check takes however long it takes to call `f` - and then it will copy the rest of the list, and do a recursive call on that copy, which in this case is an empty list. so `filter(1)` takes `f + copy(0) + filter(0)` operations, where `copy(n)` is how long it takes to copy a list, and `f` is how long it takes to check whether an element should be included, assuming it takes the same amount of time for each element.

What about `filter(2)`? It will do 1 check, then copy the rest of list and call `filter` on the remainder: `f + copy(1) + filter(1)`.

You can see the pattern already. `filter(n)` takes `1 + copy(n-1) + filter(n-1)`.

Now, `copy(n)` is just `n` - it takes `n` operations to slice the list in that way. So we can simplify further: `filter(n) = f + n-1 + filter(n-1)`.

Now you can try just expanding out `filter(n-1)` a few times to see what happens:

filter(n) = f + n-1 + filter(n-1)
          = 1 + n-1 + (f + n-2 + filter(n-2))
          = f + n-1 + f + n-2 + filter(n-2)
          = 2f + 2n-3 + filter(n-2)
          = 2f + 2n-3 + (f + n-3 + filter(n-3))
          = 3f + 3n-6 + filter(n-3)
          = 3f + 3n-6 + (f + n-4 + filter(n-4))
          = 4f + 4n-10 + filter(n-4)
          = 5f + 5n-15 + filter(n-5)
          ...

Can we generalize for `x` repetitions? That `1, 3, 6, 10, 15`... sequence is the triangle numbers - that is, `1`, `1+2`, `1+2+3`, `1+2+3+4`, etc. The sum of all numbers from `1` to `x` is `x*(x-1)/2`.

          = x*f + x*n - x*(x-1)/2 + filter(n-x)

Now, what is `x`? How many repetitions will we have? Well, you can see that when `x` = `n`, you have no more recursion - `filter(n-n)`=`filter(0)`=`1`. So our formula is now:

filter(n) = n*f + n*n - n*(n-1)/2 + 1

Which we can simplify further:

filter(n) = n*f + n^2 - (n^2 - n)/2 + 1
          = n*f + n^2 - n^2/2 + n/2 + 1
          = n^2 - n^2/2 + f*n + n/2 + 1
          = (1/2)n^2 + (f + 1/2)n + 1

So there ya have it - a rather detailed analysis. That would be `Θ((1/2)n^2 + (f + 1/2)n + 1)`... assuming `f` is insignificant (say `f`=1) that gets to `Θ((1/2)n^2 + (3/2)n + 1)`.

Now you'll notice, if `copy(n)` took a constant amount of time instead of a linear amount of time (if `copy(n)` was 1 instead of `n`), then you wouldn't get that `n^2` term in there.

I'll admit, when I said `Θ(n^2)` initially, I didn't do this all in my head. Rather, I figured: ok, you have `n` recursive steps, and each step will take `n` amount of time because of the `copy`. `n*n = n^2`, thus `Θ(n^2)`. To do that a bit more exactly, `n` shrinks at each step, so you really have `n + (n-1) + (n-2) + (n-3) + ... + 1`, which ends up being that same figure as above: `n*n - (1 + 2 + 3 + ... + n)` = `n*n - n*(n-1)/2` = `(1/2)n^2 + (1/2)n`, which is the same if I had used `0` instead of `f`, above. Likewise, if you had `n` steps but each step took `1` instead of `n` (if you didn't have to copy the list), then you'd have `1 + 1 + 1 + ... + 1`, `n` times, or simply `n`.

But, that requires a bit more intuition so I figured I'd also show you the brute force method that you can apply to anything.

Problem

``` def filter(f, lst): if lst == []: return [] if f(lst[0]): return [lst[0]] + filter(f, lst[1:]) return filter(f, lst[1:]) def my_reverse(lst): # Reverse the list def reverse_helper(x,y): if x == []: return y return reverse_helper(x[1:], [x[0]] + y) return reverse_helper(lst, []) def revfilter_alpha(f, lst): # Reverse and filter ... return my_reverse(filter(f, lst)) def revfilter_beta(f, lst): # Reverse and filter ... if lst == []: return [] return revfilter_beta(f, lst[1:]) + ([lst[0]] if f(lst[0]) else []) ``` Could someone explain to me how to determine the running time in Big Θ notation for these? I've read quite a few things but still have no idea where to begin. In `filter`, I think it is Θ(n^2) because it checks each element in list of size n with the predicate function f with n recursive calls so n*n. `revfilter_beta` looks pretty similar just reversing while filtering so wouldn't this also be Θ(n^2)? `revfilter_alpha` does filter then a reverse, so wouldn't this be n^2*n^2 = Θ(n^4)? Does anyone have any thoughts?

Original source