Help with find recurrence relation running time.

1.1k Views Asked by At

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using the expansion into series (substitution), or induction.

int func1(A,n) {
    for i=1 to n^2-5 
        for j = 1 to floor( n / 2 ) 
            A[ i mod n ]= A[ i mod n ] - A[ j ] + A[ i mod n ] * A[ j ]; 
    y = func1( A, n - 3 ); 
    return y;

My thoughts thus far:

I got the double summation to get the running time of the nested for loops as theta(n^3).

Then I set up the formula $T(n) cn^3+T(n-3)$. I just set that up based on an example but I guess that makes sense with the for loop time + the recursive element that can be expanded to show the recursion.

Then I expand it to $cn^3+cn(n-3)^3+T(n-6)$. again I saw an example increment the term in this way so I don't really understand why it's n-6 (if that's even correct).

Then I see examples plugging in n/2. Because that's the middle term if its $func(A, n)$?. so $n/2(n^3)$ is gonna be omega of $n^4$.

Thanks for any help/hints/links