Explain time complexity (Big O) of this recursive function

Question

This is a practice problem from AlgoExpert. Input is a "special" array that is a non-empty array that contains either integers or other "special arrays". The product sum of a "special" array is the sum of its elements, where "special" arrays inside it are summed themselves and then multiplied by their level of depth.

O(n) time, where n is the total number of elements in the array
O(d) space, where d is the greatest depth of "special" arrays in the array
O(d) space
def productSum(array, multiplier=1):
   sum = 0
   for element in array:
       if type(element) is list:
           sum += productSum(element, multiplier + 1)
       else:
           sum += element
   return sum * multiplier

I don't understand why the time complexity of this function is O(N)?

If the element you're iterating through in the for statement is another array, then isn't it a for statement within for statement O(N^2)?

Or, I guess the inner for statement, the length of the array is unknown.....

but still I don't understand why it's just O(N). What if you get an input where every single element is an array, and all those inner array lengths are even longer than initial input array length?

Or is this some amortized analysis stuff?

Thanks!

Answer 1

This is a linear time algorithm because it's running time is linear in the input size n. Observe that if the original input array is [a,b,c,d], where a,b, and c are integers, and d is the array [d1,d2,d3,d4,d5], then the total length n of the original input is not 4 (times the number of bytes for each element), but is on the order of 3+5=8 (times the number of bytes for each element). In general, your algorithm does a constant amount of work for each element, and hence runs in time O(n) for each element of length n (an element could be an integer or an array itself), and hence in time O(n) for an input of length n.

There is a nested for-loop, but the depth of recursion can be larger than 2. For example, the input can be [1,2,3,[4,5,[6,[1,2]]]], which essentially amounts to a quadraply-nested for loops.

The running time T(n) of an algorithm is defined to be the worst-case running time, over all inputs of size n. The input size n is the number of bits needed to represent the input. An element in the original input that is a subarray of size n will consume not one unit of space but O(n) units of space.