Asymptotic time complexity of Recursive function

[GeorgeCostanz]

Homework Statement

I've been asked to develop a recursive function and then analyze the asymptotic time complexity.

f(N) = 0, if N < N1

f(N1) = C1

f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1

Homework Equations

We're to assume that:

s1 = s2 = 0

m2 = m4 = 1

d1 = d2 > 1

The Attempt at a Solution

the user enters N1 C1 A1 M1 M2 M3 M4 D1 D2 S1 S2 and then ARG

int Recursion_Plus(int ARG)
{

    if (ARG < n1)
    {
        return 0;
    }
    else if(ARG == n1)
    {
        return c1;
    }
    else if(ARG > n1 )
    {
        return a1 + m1 
        * 
       Recursion_Plus(m2*ARG/d1 - s1) 
       + 
       m3*Recursion_Plus(m4*ARG/d2 - s2);
    }

}

I've tested my recursive function against the instructor's program and it works exactly the same so I've moved on to my analysis, where I've hit a wall.

I'm struggling to wrap my brain around this so bear with me please.

My attempt at a partial solution:

a1 & m1 & m3 are insignificant because they're outside the recursive call

a1 + m1*___ = 1 unit of time

m1*___ = 1 unit of time

adding the 2 recursive calls together is 1 unit of time

m3*___ = 1 unit of time

This is where i get lost. From the instructions we're given, both recursive functions will be called using the same # every time, and every successive number that the recursive function calls will be smaller than the last because d1 = d2 > 1.

So the larger ARG is (in comparison to n1 & c1), the longer it takes to complete and the larger the result will be. So the algorithm takes O(n) time.

I'd appreciate it if anyone could let me kno if I'm on the right track or completely lost. Thanks

 

[pbuk]

So the larger ARG is (in comparison to n1 & c1), the longer it takes to complete and the larger the result will be. So the algorithm takes O(n) time.

Why not O(n²), or O(2ⁿ), or O(log[n])?

I'm afraid you are completely lost, although it happens that you have the right answer. Forget about the time it takes to perform calculations*, the important thing is the number of times the function is called.

If you have a mathematical background, let the number of times the function is called when ARG=n be K(n). Find a recurrence relation for K(n).

If your maths is less formal, here is a clue: when ARG ≤ N1 time ≈ k. When ARG ≤ N1 x D1 time ≈ k + k + k. When ARG ≤ N1 x D1 x D1 time ≈ k + 3k + 3k. When When ARG ≤ N1 x D1² time ≈ k + 7k + 7k...


* you can do this becase ARG is an int so calculations are performed in constant time. If the problem involved e.g. arbitrary precision arithmetic this would not be the case.