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?

Pokorny

I don't think the code works. For example: nextnext isn't defined. – Crepe

@PaulHankin. Sorry that was a typo. Fixed it – Pokorny

duplicate of #38950119 – Caterinacatering

("The * 1-product" can be placed in the single parameter method where it doesn't need to be controlled. Turning expression to StringBuilder impedes readability and doesn't really help: "each" String gets printed. If factor <= previous, next <= factor implies next <= previous. Out of principle, I'd initialise factor = Math.min(dividend/2, previous).) – Rice

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))

Tenia

Why is it d*F(N/2), is it because at worst case a factor could divide the original number into half and there are d prime factors. Also according to master theorem d cannot be greater than 2. Also where is O(N) coming from? Is it because at worst it could be multiple of N numbers? – Pokorny

@Pokorny You are correct about the reason for d*F(N/2). Case 1 example says a can be 8, so it is incorrect to say it can't be more than 2. O(N) is because the for loop is iterated around N times. – Tenia

BTW, the first bound is tighter, because the number of factorizations does not grow faster than O(N) (proof?), so overall it's no worse than O(N^2). Also, I feel that it's really O(N log N) at worst, but can't prove it now. – Tenia

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))

Piccadilly

Answer 3

The time complexity is calculated as : Total number of iterations multiplied 
by no of sub iterations^depth.So over all complexity id Y(n)=O(no of
dividends)*O(number of factorization )+O(no of (factors-2) in loop);

Example PrintFactors(12) 12 * 1 ,6 * 2, 4 * 3, 3 * 2 * 2
O(no of dividends)=12
O(number of factorization)=3
O(no of factors-2){ in case of 3 * 2 * 2)=1 extra

Over all: O(N^logbase2(dividends))

Piotr