Is this correct time complexity?

Question

I did this as a solution to one of the leetcode problems, but I'm not sure what the complexity of my algorithm is.

public String countAndSay(int n) {
        if (n == 1) return "1";
        String pre = countAndSay(n-1);
        char[] prev = pre.toCharArray();
        int len = prev.length;
        if (len == 1 && prev[0] == '1') return "11";
        int idx = 1;
        int rep = 1;
        String res = "";
        while (idx <= len) {
            if (idx == len) {
                res += (Integer.toString(rep) + prev[idx-1]);
                break;
            }
            if (prev[idx-1] == prev[idx]) rep++;
            else {
                res += (Integer.toString(rep) + prev[idx-1]);
                rep = 1;
            }
            idx++;
        }
        return res;
    }

Since the recursion takes place n times and the loop is O(n), I feel like it should be O(n^2). Is that correct? If not, can you please explain why?

Answer 1

Here are a few facts:

• The method calls itself recursively on input n-1.
• The method produces the sequence known as look-and-say sequence.
• The length of the resulting string grows exponentially with base λ, where λ = 1.303577269034... is Conway's constant, so the length is O(λ^n).
• The loop is quadratic on the length of the string (because of the repeated string concatenations), so we have O((λ^n)^2) = O((λ^2)^n) for the loop.

Hence we can derive the following recurrence relation:

T(0) = 1
T(n) = T(n-1) + O((λ^2)^n)

The asymptotic behaviour of this relation is given by

T(n) ∈ Θ((λ^2)^n) = Θ(1.6993^n)

If you use a StringBuilder instead of doing the evil repeated string concatenations, you can get it down to Θ(λ^n) which would also be asymptotically optimal for this problem.