What is the time complexity of this algorithm

Question

Write a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency. PrintFactors(12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2

public void printFactors(int number) {
    printFactors("", number, number);
}

public void printFactors(String expression, int dividend, int previous) {
    if(expression == "")
        System.out.println(previous + " * 1");

    for (int factor = dividend - 1; factor >= 2; --factor) {
        if (dividend % factor == 0 && factor <= previous) {
            int next = dividend / factor;
            if (next <= factor)
                if (next <= previous)
                    System.out.println(expression + factor + " * " + next);

            printFactors(expression + factor + " * ", next, factor);
        }
    }
}

I think it is

If the given number is N and the number of prime factors of N = d, then the time complexity is O(N^d). It is because the recursion depth will go up to the number of prime factors. But it is not tight bound. Any suggestions?

Answer 1

2 ideas:

The algorithm is output-sensitive. Outputting a factorization uses up at most O(N) iterations of the loop, so overall we have O(N * number_of_factorizations)

Also, via Master's theorem, the equation is: F(N) = d * F(N/2) + O(N) , so overall we have O(N^log_2(d))

Answer 2

The time complexity should be:

number of iterations * number of sub calls ^ depth

There are O(log N) sub calls instead of O(N), since the number of divisors of N is O(log N)

The depth of recursion is also O(log N), and number of iterations for every recursive call is less than N/(2^depth), so overall time complexity is O(N ((log N)/2)^(log N))