4
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)?

ggorlen
  • 44,755
  • 7
  • 76
  • 106
user737163
  • 431
  • 3
  • 9
  • 1
    Voted to reopen. This is a pretty good question--shows an attempt and isn't exactly trivial to calculate even given baseline big O knowledge, which OP clearly shows. The algorithm is poorly designed: the `L[1:]` is O(n) right there, and that's incurred `n` times, so your baseline complexity is at least O(n*n). Next, add in the recursion for sublists. Also, you have a bug with `type` and `if L == []` should be `if not L` to avoid an object allocation. Instead of passing in an index, I'd use a loop here (recursion is generally only useful when the problem size shrinks by a large factor). – ggorlen Jan 27 '21 at 18:28
  • So basically the first part (checking if the element is a list) doesn't really change complexity since every element in the list calls a function with a list as an argument that depends on n? Therefore the complexity is O(n^2)? @ggorlen – user737163 Jan 27 '21 at 18:37
  • This algorithm comes from a book and it isn't mine btw. So what you are trying to say is that slicing is O(n) due to index shifting, and this occurs for every element in the list; thus O(n^2)? Did I now understand correctly? @ggorlen – user737163 Jan 27 '21 at 18:47
  • But technically then, if every element of this list is a list wouldn't that mean it is O(n^3)? Since we have the naive slicing O(n^2) pattern for every element in the list L? @ggorlen – user737163 Jan 27 '21 at 18:56
  • Oh I get it now. So that means it can then be O(d^2 * n) if all elements are lists. So what is the bigO at the end? O(n^2) or O(d^2)? It depends on what list has more elements or what? @ggorlen – user737163 Jan 27 '21 at 19:06
  • What I don't seem to understand is how the slicing problem doesn't affect list d. Since d is called as its own function and then the slicing happens just like it happens for n. @ggorlen – user737163 Jan 27 '21 at 19:13
  • How is there no slicing in that call though, sorry but I am really confused now? It will also run the above function just for the inner list d and it will keep on slicing until it is an empty list? @ggorlen – user737163 Jan 27 '21 at 19:17
  • Oh no... I just figured out what you are saying. It returns 1 if the list is flat which means the function is run d times aka depth times multiplied by the function that has O(n^2) due to slicing. Which means O(d*n^2). I think I got it fully now, thank you for your patience! @ggorlen – user737163 Jan 27 '21 at 19:19
  • Mind you, the question is poorly designed; the complexity of `L[1:]` is basically an implementation detail of Python. The same question with numpy arrays instead of lists would have a completely different answer, because `L[1:]` is constant-time with numpy arrays. – Jiří Baum Jan 28 '21 at 09:52
  • Note that the function recurses into all lists in the structure; it's a problematic implementation of `len(flatten(L))` which manages to make multiple copies of most of the elements. – Jiří Baum Jan 28 '21 at 09:56
  • I think we would need to know some restrictions on the input to be able to analyse the time complexity, because there are some inputs (e.g. lists containing references to themselves) on which the algorithm does not terminate (in theory). If reference cycles are banned, how about aliases? – kaya3 Jan 28 '21 at 10:38
  • I think aliases don't make any difference; other than cycles, it's all good. We just need to know the size and shape of the input. – Jiří Baum Jan 28 '21 at 10:52

1 Answers1

0

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.

ghchoi
  • 4,812
  • 4
  • 30
  • 53
  • Per the comments on the question, `L[1:]` makes a copy; it's not a constant-time operation... – Jiří Baum Jan 28 '21 at 11:17
  • @sabik It depends. That would be much cheaper than recursive calls. I think its ignorable. Or, we may have different time complexity for merge sort, aren't we? Because it has to allocate and copy. Also, the questioner may not consider that because (s)he asks whether it is `O(mn)` or `O(n)`. – ghchoi Jan 28 '21 at 11:30
  • Good implementations of merge sort do not make _n²_ copies... – Jiří Baum Jan 28 '21 at 11:41
  • @sabik Ah, sorry. Merge sort was a bad example... However, memory copy should be very efficient. Python list is dynamic array which is randomly accessible. Thus, copy can be done in chunk by chunk manner, not one by one for each element. – ghchoi Jan 28 '21 at 12:04