Time complexity of some python programs

[Lucaci Andrew]

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)
or
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.
Cheers:icon_wink:

[Lucaci Andrew]

I forgot to post my second source code:

def f(n,x):     
    m = n     
    found = False     
    while m!=0:         
        c = m - m/3*3         
        if c==1: foud=True         
        m = m/3     
        found = False     
    while n!=0 and not found:         
        if x[n]==7: found=True         
        else: n=n-1     
    return found

From my point of view, the time complexity of this function is O(n), having in consideration the fact that it has 2 whiles, which both are executed n times, so n+n which is 2n, O(n). Am I correct, or am I wrong.:d

[Gribouillis]

I would say that the time complexity of the first function is O((j-i) Log(j-i)). The rough argument is this: it is obvious that the number of 'print' only depends on j-i. Call f(z) the number of items printed when prel(x, i, j) is called with an interval length z = j-i. There are z explicit prints in the function, and the function is recursively called 3 times with an interval of length about z/3. It means that f(z) = z + 3 f(z/3) approximately. The mathematical function which satisfies exactly this relation is f(z) = z log(z)/log(3). So this must be roughly the number of prints.

[Lucaci Andrew]

10x mate, I sure i'm pissed rite now, that clearly I'm not into computing time complexity, but regardless to my exam, I hope I'll get it in the end, well, 1 day left:d