Big-Theta(n^m) recursive

Question

I'm trying to implement an algorithm with time complexity in Big-Theta(n^m), n and m are natural numbers.

My first solution:

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);
  }
}

My second solution:

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);
   }
}

When I analyze my second solution, called algo(n,m,m), I get T(i) = n * T(i-1), i > 0. With T(0) = constant time I get T(i) = n^m. So I think my second solution is right, but I don't know what is wrong with my first solution.

Answer 1

For your first algorithm,

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

will basically call algo for total of m * (m-1) / 2 times, each algo has a O(n) loop, so, the total complexity will be O(n * m ^ 2).

Or in other words, for the first algorithm, it's similar to T(i) = n + T(i-1), where i = 0, ..., m.