I have trouble analyzing runtimes of recursive algorithms sometimes, so If any of you can help, I would very much appreciate it. In the code below, I am just enumerating the prime decomposition of any positive integer.
I know the isPrime() function takes O(n) time - and I know how I can improve it, but for the sake of this exercise, I am just using the linear time implementation. What I am having trouble with is analyzing the runtime of the recursive calls to decompose() function. It is confusing me because the subproblems that I have are not of the same size (E.x: If I consider prime factors of 30, the first call considers 30/2 = 15. The second time, the subproblem size is divided by 3, and the third time by 5 and we are done. So, I am confused because it is equal sub-problem size like merge sort or quick sort or other divide-and-conquer algorithms of the like.
I would appreciate help understanding the runtime of this algorithm.
import java.util.*;
public class PrimeDecomposition {
public static void main(String[] args) {
System.out.println(isPrime(2));
print(findPrimeDecomposition(36));
}
public static List<Integer> findPrimeDecomposition(int n) {
List<Integer> output = new ArrayList<>();
decompose(n, 2, output);
return output;
}
public static void decompose(int n, int i, List<Integer> decomposition) {
if (n <= 1) return;
if (isPrime(n)) {
decomposition.add(n);
return;
} else {
if (n % i == 0 && isPrime(i)) {
decomposition.add(i);
decompose(n / i, i, decomposition);
} else {
decompose(n, i + 1, decomposition);
}
}
}
public static void print(List<Integer> list) {
for (int num : list) {
System.out.print(num);
System.out.print(" ");
}
System.out.println();
}
public static boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
}