Big O of recursive function that counts the elements in a nested list

user_12717059 0
Viewed 301
def f(L):
 if L == []:
  return 0
 return (f(L[0]) if type (L[0]) == list else 1) + f(L[1:])

I'm having a bit of trouble determining big O for recursive functions. I have a feeling this function is O(n*m) where n is the length of the list L and m is the length of list elements in list L. Am I correct or is this function just O(n)?

recursion big-o python
1 Answers

Let us have the other function g(l) which does what f(L) does but with l, a list element of L.

Expansion of all recursive calls would be like:

step 0: f(L)
        |        \
step 1: g(L[0]) + f(L[1:])
                  |        \
step 2:           g(L[1]) + f(L[2:])
                            |        \
step 3:                     g(L[2]) + f(L[3:])
                                      |        \
                                      ...       ...

The number of f nodes are O(n).

The number of g nodes are O(n).

For each step, f node takes O(1) and g node takes O(m) because

step i.0: g(l)
          |   \
step i.1: 1 +  g(l[1:])
               |       \
step i.2:      1 +      g(l[2:])
                        |       \
step i.3:               1 +      g(l[3:])
                                 |       \
                                 1 +      ...

I believe, then, O(n * 1 + n * m) = O(n*m).

Please correct me if I was wrong.

user_42271750
Related