692 views
4 votes
4 votes

Consider the code below, defining the functions $f$ and $g$:

f(m, n) {
    if (m == 0) return n;
    else {
        q = m div 10;
        r = m mod 10;
        return f(q, 10*n + r);
    }
}
g(m, n) {
    if (n == 0) return m;
    else {
        q = m div 10;
        r = m mod 10;
        return g(f(f(q, 0), r), n-1);
    }
}

How much time does it take to compute $f(m, n)$ and $g(m, n)$?

2 Answers

0 votes
0 votes
f(m, n) = O(log m) in this case logm function call

g(m, n) = O(n · log m)

Related questions