Computational complexity and recursion - Is this analysis correct?

Hi! I have a doubt about this resolution of this algorithm analysis, specifically referred to the return min(L[i:j+1]): why is it considered O(n)?: it always refers to a defined slice, with a limited possible dimension (j<=i+2)

Solution 1:

For simplicity, consider size of the list to be a power of 3.

Algorithm

if j-i+1 <= 3:
    # Compute their minimum
    return min(i:j+1)

The if statement forms the base case. Time complexity of above statements is O(1). However, the if statement will be executed n times.

Recursion Tree

                                     T(n)
                                       |
                 ______________________|______________________
                |                      |                      |
                |                      |                      |
             T(n/3)                 T(n/3)                 T(n/3)
                |                      |                      |
         _______|_______        _______|_______        _______|_______
        |       |       |      |       |       |      |       |       |
        |       |       |      |       |       |      |       |       |
     T(n/9)  T(n/9)  T(n/9) T(n/9)  T(n/9)  T(n/9) T(n/9)  T(n/9)  T(n/9)

        .       .       .      .       .       .      .       .       .
        .       .       .      .       .       .      .       .       .
        .       .       .      .       .       .      .       .       . 
        .       .       .      .       .       .      .       .       .    
      T(1)    T(1)    T(1)   T(1)    T(1)    T(1)   T(1)    T(1)    T(1)    --- (n/3) * T(1)      

It should be obvious from the recursion tree, that for an array of size n, if statement will be executed n/3 times. Hence, overall complexity of if statement is O(n).

The reason if is executed n/3 times and not n is that recursion ends when we encountered an error of size 3. If the the recursion came to an end when we encountered an error of size 1, then it would have been executed for n times.