Can anyone explain how to calculate the complexity of the following algorithm?

Question

I have this algorithm and i have to find its complexity. I have in mind some things but until now the only complexity i found was the "worst" case which i assumed is the one that each time time all the elements go in one array and the other is empty.

public class Test {
    //this input served as an example to find out if the algorithm is running correctly 
    static char[] pin = {'A','B','C','D','E','F','G','H'};
    
    public static void Post_to_PreOrder(char[] P, int first, int last){
        System.out.println(P);
        if (first <= last){
        System.out.println(P[last]);
        int i = 0;
        while (P[i] < P[last]){
            i++;
        }
        int k = i;
        char[] m =  new char[k];
        for (i = 0; i<k; i++){
            m[i] = P[i];
        }
        char[] M = new char[P.length - k - 1];
        for (i = k; i<P.length -1; i++){
            M[i-k] = P[i];
        }
        Post_to_PreOrder(m, 0, m.length-1);
        Post_to_PreOrder(M, 0, M.length-1);
    }
    }

    public static void main(String[] args){
        Post_to_PreOrder(pin, 0, pin.length-1);
    }
}

From what i've been taught up until now, to find the complexity of an algorithm we have to check the worst, best and "average" cases (sorry if naming is wrong i am translating it from Greek), excluding the case in which a function is provided. In this case i can't find a function for complexity so i guess i'm stuck with checking the cases. But to be sure that my "worst" case is actually the worst i have to prove it. This is where hopefully you guys come in and give me tips on how to generally deal with these type of questions and maybe an answer to this problem explaining the reasoning behind the solution? Thank you all in advance!

Answer 1

The algorithm you have provided is a recursive implementation of converting a postfix expression to a prefix expression, where a postfix expression is given as an array of characters. The algorithm works by recursively splitting the postfix expression into two sub-expressions until a single character is left, and then reversing the order of the sub-expressions and the operator at each recursive call to obtain the corresponding prefix expression.

The time complexity of the algorithm can be analyzed as follows:

1. The base case of the recursion is when the sub-expression contains only one character, which takes constant time O(1) to process.
2. In the general case, the algorithm splits the postfix expression into two sub-expressions based on the position of the last character in the postfix expression. The loop that finds the position of the last character takes O(n) time, where n is the length of the sub-expression.
3. The algorithm then creates two new sub-expressions by copying the characters from the original sub-expression into two new arrays. This takes O(n) time in total, where n is the length of the original sub-expression.
4. The algorithm then recursively calls itself on the two new sub-expressions, which results in two smaller sub-problems that are each a fraction of the original problem size. The time complexity of each recursive call is therefore proportional to the size of the sub-problem, which is given by (n/2) in the average case.
5. The recursion continues until the base case is reached, at which point the sub-expression has length 1, and the recursion returns back up the call stack.

The total time complexity of the algorithm can be expressed as a recursive function:

T(n) = 2T(n/2) + O(n)

where T(n/2) is the time complexity of each recursive call, and O(n) is the time complexity of the split and copy operations. This is a standard divide-and-conquer algorithm, and its time complexity can be solved using the Master Theorem, which gives:

T(n) = O(n log n)

Therefore, the time complexity of the given algorithm is O(n log n), where n is the length of the input postfix expression.