scala - Complexity estimation for simple recursive algorithm -

i wrote code on scala. , want estimate time , memory complexity.

problem statement

given positive integer n, find least number of perfect square numbers (for example, 1, 4, 9, 16, ...) sum n.

for example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

my code

def numsquares(n: int): int = {   import java.lang.math._    def traverse(n: int, ns: int): int = {     val max = ((num: int) => {       val sq = sqrt(num)       // perfect square!       if (sq == floor(sq))         num.toint       else         sq.toint * sq.toint     })(n)      if (n == max)       ns + 1     else       traverse(n - max, ns + 1)   }    traverse(n, 0) } 

i use here recursion solution. imho time complexity o(n), because need traverse on sequence of numbers using recursion. right? have missed anything?