Как рассчитать сложность времени?

Question

Я рассмотрел некоторые основные понятия расчета временных сложностей. Я хотел бы узнать временную сложность приведенного ниже кода.

Я думаю, что временная сложность будет O (журнал п * п). Он все еще может быть неправильным, и я хочу знать точный ответ и как прийти к нему. Спасибо :)

function(int n){ 
    if(n == 1) return; 
    for(int i = 1; i <= n; i++) 
     for(int j = 1; j <= n; j++) 
      printf("*"); 
    function(n-3); 
    } 

Answer 1

Два вложенных циклов с п итераций дают O (N^2). Рекурсия вызывает сама функция для O (n) -time, так как она уменьшает n для константы 3, поэтому она называется n/3 + 1 = O (n) раз. В целом, это O (n^3).

Константа логарифма в вашем результате будет в случае, если функция вызывается со значением n/3.