Big-Theta (n^m) recursive

Question

Я пытаюсь реализовать алгоритм с временной сложностью в Big-Theta (n^m), n и m - натуральные числа.

Мой первый раствор:

algo(n,m,i){ // called with algo(n,m,1) 
    if (i < m){ 
    algo(n,m,i+1) 
    } 
    for i = 1 to n{ 
    print(do something in constant time); 
    } 
} 

Мой второй раствор:

algo(n,m,i){ //called with algo(n,m,m) 
    if (i > 0){ 
     for j = 1 to n{ 
     algo(n,m,i-1) 
     } 
    }else{ 
    print(do something in constant time); 
    } 
} 

Когда я анализирую мое второе решение, называется algo(n,m,m), я получаю T(i) = n * T(i-1), i > 0. С T (0) = постоянное время я получаю T(i) = n^m. Поэтому я считаю, что мое второе решение правильно, но я не знаю, что не так с моим первым решением.

Answer 1

Для первого алгоритма,

if (i < m) 
    algo(n, m, i+1) 

будет в основном называют algo для общей m * (m-1)/2 раз, каждый algo имеет O(n) петлю, так что общая сложность будет O(n * m^2).

Или, другими словами, для первого алгоритма это похоже на T(i) = n + T(i-1), где i = 0, ..., m.