CODEWITHSUNDEEP
pythonbig-o
Roy Levy
Roy Levy

Reputation: 730

Understanding complexity of this python function

What is the complexity ("big O" notation) of the function f(L), where n is the length of L? I can understand that the running time of the inner function is constant. Therefore is it O(n)?

This function is taken from a past test in the course "Introduction to CS Python".

def f(L):
    def f_helper(L,i):
        if i:
            return f_helper([L,L], i-1) + f_helper([L,L], i-1)
        return len(L)
    return f_helper(L,3)

Upvotes: 1

Views: 72

Answers (2)

Hugh Bothwell
Hugh Bothwell

Reputation: 56694

A quick approach is to instrument the function and run it:

def f(L):
    print("Call f({})".format(repr(L)))
    def f_helper(L,i):
        print("{}call f_helper({}, {})".format("  "*(4 - i), repr(L), repr(i)))
        if i:
            res = f_helper([L, L], i-1) + f_helper([L, L], i-1)
            print("{}return {}".format("  "*(4 - i), res))
            return res
        else:
            res = len(L)
            print("{}return {}".format("  "*(4 - i), res))
            return res
    return f_helper(L,3)

then

>>> f("LLL")

Call f('LLL')
  call f_helper('LLL', 3)
    call f_helper(['LLL', 'LLL'], 2)
      call f_helper([['LLL', 'LLL'], ['LLL', 'LLL']], 1)
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
      return 4
      call f_helper([['LLL', 'LLL'], ['LLL', 'LLL']], 1)
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
      return 4
    return 8
    call f_helper(['LLL', 'LLL'], 2)
      call f_helper([['LLL', 'LLL'], ['LLL', 'LLL']], 1)
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
      return 4
      call f_helper([['LLL', 'LLL'], ['LLL', 'LLL']], 1)
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
        call f_helper([[['LLL', 'LLL'], ['LLL', 'LLL']], [['LLL', 'LLL'], ['LLL', 'LLL']]], 0)
        return 2
      return 4
    return 8
  return 16

... it should be immediately apparent that the original content of L has no effect on the number of calls made.

Upvotes: 2

Prune
Prune

Reputation: 77900

First, note the base case, which is essentially

if i == 0:
    return len(L)

where L is [L, L] from the previous instance. If L is originally a list, tuple, string, ... then [L, L] will be a list of length 2, so len(L) will be O(1).

Next, do you have any object you could pass as L for which [L, L] would be anything other than a pair of references to the input parameter? If not, then every instance is merely a pair of calls of O(1).

To watch this in action, add a simple tracing statement as you enter the function:

print("ENTER", i, L)

and watch what you get at each function call.

Is that enough to get you to the answer?

Upvotes: 2

Related Questions