What is the time complexity of this Scheme function?

Question

What is the time complexity? Why?

(define (mult a b)
      (define (internal a accum)
        (if (= a 1) accum
            (internal (- a 1) (+ accum b))))
      (internal a b))

    (define (to-the-power-of m n)
      (define (internal x accum)
        (if (= x 0) accum
            (internal (- x 1) (mult accum m))))
      (internal n 1))

Answer 1

Assuming addition and multiplication are both counted as a single operation, this function performs O(m^n) operations.

First consider the mult function. It (mult a b) will perform exactly a-1 additions. Since, the asymptotic growth is the same, lets approximate this by a, for mathematical simplicity.

Now for the to-the-power-of function, this performs n calls to the mult function. These calls are to (mult 1 m), yield m, then to (mult m m), yielding m^2, then to (mult m^2 m), yielding m^3 and so on upto m^n. So the total number of operations performed here is the sum m^0 + m^1 + ... + m^n. This is (m^n - 1) / (m-1) which grows as m^n.

Answer 2

the time complexity for the mult part can be found like this:

to calculate (mult a b), (internal a accum) is called until a = 1 so we have some kind of tail recursion (loop) that iterates over a.

we thus know that the time complexity of (mult a b) is O(a) (= linear time complexity)

(to-the-power-of m n) also has an (internal x accum) definition, that also loops (until x = 0)

so again we have O(x) (= linear time complexity)

But: we didn't take into account the time needed for the function calls of internal...
In internal, we use the (mult a b) definition which is linear in time complexity so we have the following case: in the first iteration mult is called with: (mult 1 m) --> O(1)
second iteration this becomes: (mult m m) --> O(m)
third iteration: (mult m² m) --> O(m*m) and so on It is clear that this grows until n = 0 (or in internal this becomes x = 0)

thus we can say that the time complexity will depend on m and n: O(m^n)

[edit:] you can also take a look at a related question I asked earlier: Big O, how do you calculate/approximate it? which may give you a clue how you can handle the approximation more generally