Сложность времени для случайного вызова

Question

Какова будет временная сложность для данного кода

int func(int n){
     int i;
     if(n<=0)
       return 0;
     else
     {
         i=random(n-1);
         return func(i)+func(n-1-i);
     }
       
 }

Думаю, O (n), но как я могу это доказать?

Answer 1

Чтобы доказать, что ваша временная сложность равна O (n), вам нужно доказать, что

return func(i)+func(n-1-i);

не будет вызываться более n раз. Пока n уменьшается как минимум на 1 (i - int, от 0 до n, а n уменьшается каждый раз на i + 1) при каждом вызове, вы будете использовать эту строку максимум n раз.

И поскольку без рекурсивного вызова ваша временная сложность равна O (1), то с рекурсивным вызовом ваша временная сложность равна O (n), и вы не сможете вычислить лучшую, пока случайные может каждый раз давать 0.