In the book, ( I own the java version) the recurrence equation is described as T(n)<=4T(n-1) and states that the “time spent within the function, not including recursive calls”, is O(1).
However, isn’t each function call doing O(n) operations since we’re using the for loop to get the “char c” ,the partialMnemonic? ( I mean, for each function call, we’re looping n times and trying to get the char c n times, right?)
So should the recurrence equation be
T(n) = 4T(n-1) + O(n)
not
T(n) = 4T(n-1) + O(1)
Thank you! I’m very curious about this one because I had a similar question about the recurrence equation for generating all permutations…