Search code examples
code-complexity

Measuring code complexity of a recursive function

According to my professor, this code is Teta(n^n)

Measuring line by line i cant discover myself why its n^n complexity

this is the code

any(v[], n, degree){
   for(i=0; i<degree; i++){
      any(v,n-1,degree)
   }
}

i have been making myself.

any(v[], n, degree){
   for(i=0 - C; i<degree c(n+1); i++ cn){ 
      any(v,n-1,degree) n(T(n-1))
   }
}

It is 2c+2cn+n(T(n-1)).

Solution

  • To start, it looks like this would actually be infinite since it doesn't break or return at n==0. Assuming that the algorithm does return at n==0 (it would have to in an if statement that is currently missing):

    T(n) = degree*T(n-1), where T(0) = 1 and T(1) = degree

    This reduces to O(degree^n)

    I'm not really sure where the n^n comes from. Unless I did the maths wrong.