def prel(x, i, j): if (i < j - 1): k1 = (j - i + 1) / 3 k2 = 2 * k1 prel(x, i, i + k1) prel(x, i + k1 + 1, i + k2) prel(x, i + k2 + 1, j) for k in range(i, j): print x[k] else: print x[i]
I'm wondering what is the time complexity of this function. This is one of the examples which was given to me by my IT professor, as a "might be subject" on my next exam. Frankly, I have to admit that I'm bad at computing and calculating time complexitys. But, I have tried something, and I want to know if i'm right.
This program, I repeat, is an example, not an actual working code.
Ok, so.. From my point of view, the time complexity of this code is O(n^4), because having 1 for in the main function, and then, recursively called 3 times that's like 4 fors nested. So, there are two cases:
1. Best case, when it doesn't meets the requirements of the if condition, and therefore jumps to the else part, meaning print x, and here the O(1)
2. Worst case, when it does meet the requirements, and enter the if condition.
Please, if anyone of you are in good knowing of this part of time complexity, respond to this thread, in order for me to know where are my mistakes, and what approach is suited, and should I take for such a function.