0

I've seen so many time complexity problems but none seem to aid in my understanding of it - like really get it.

What I have taken from my readings and attempts at practices all seems to come down to what was mentioned here Determining complexity for recursive functions (Big O notation) in the answer coder gave - which in fact did help me understand a little more about what's going on for time complexity.

What about a function that such as this:

def f(n):
if n < 3:
    return n
if n >= 3:
    return f(n-1) + 2*f(n-2) + 3*f(n-3)

Since the function calls the function 3 times, does that mean that the time complexity is O(3^n)?

As for the space complexity, it seems to be linear hence I propose the complexity to be O(n).

Am I wrong about this?

Community
  • 1
  • 1
Danxe
  • 143
  • 7
  • You have to write down recurrence relations, and then solve them. There are some easy tricks in simple cases (eg: nested independent loops), but in general you have to do math. Reading a book that describes methods of complexity analysis might help more than picking random hard examples and guessing what methods might work. Here recurrence relations for the time complexity would give you the Tribonacci numbers which are _not_ O(3^n). – Paul Hankin Sep 05 '16 at 12:19

1 Answers1

3

Since the function calls the function 3 times

This isn't really correct, but rather lets use examples that are more exact that your ad-hoc example.

def constant(n):
    return n*12301230

This will always run in the same amount of time and is therefore O(1)

def linear(n):
    total = 0
    for x in xrange(n):
        total+=1
    return total

This has O(N) time 

def quadratic(n):
    total = 0
    for x in xrange(n):
        for y in xrange(n):
             total+=1
    return total

This runs in quadratic time O(N^2) since the inner loop runs n times and the outer loop runs n times.

There are also more specific examples for log(N), N*log(N), (2^N), etc but, going back to your question:

Since the function calls the function 3 times, does that mean that the time complexity is O(3^n)?

If the function is called 3 times, it will still be constant time for constant(x), linear for linear(x) and quadratic for quadratic(x). Importantly, O(3^n) is exponential time and is not the same as n^3. Then, we would not use a 3 as the base but a 2^n as a standard.

So your function will have a constant time for x<3. Best approximation to what your function gives, I'd run it through a timer but its recursive and difficult to compute. If you provide another, non-recursive example I'll be happy to tell you its complexity.

Hope this helps a bit, the graph doesn't do justice to how much faster 2^n grows in comparison to n^2 but it's a good start.

Time complexity

Daniel Lee
  • 7,189
  • 2
  • 26
  • 44
  • `return n*12301230` must at least read each bit of n, so its runtime will be [Θ](https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations)(length(n)). ​ ​ –  Sep 13 '16 at 06:02