recursive call from cycle: big O of algorithm and its steps

Question

I want to understand how to evaluate the complexity, big O, of below algorithm and how to approach those kind of issues of big O estimations in the future with kinda-like algorithms.

#include <iostream>
 
std::size_t const jobSize = 3;
std::size_t jobCallCounter = 0;
std::size_t jobsDoneCounter = 0;
void doJob( std::size_t jobSize )
{
    jobCallCounter++;
    for( std::size_t i = 0; i < jobSize; ++i )
    {
        jobsDoneCounter++;
    }
}
 
std::size_t recursiveCallCounter = 0;
std::size_t const cycleSize = 3;
void recursiveCall( std::size_t recursionNumber )
{
    recursiveCallCounter++;
    if( !recursionNumber )
    {
        doJob( jobSize );
    }
    else
    {
        for( std::size_t i = 0; i < cycleSize; ++i )
        {
            recursiveCall( recursionNumber - 1 );
        }
    }
}
 
int main()
{
    recursiveCall( 4 );
    std::cout << recursiveCallCounter << " recursive calls happened" << std::endl;
    std::cout << jobCallCounter << " job calls happened" << std::endl;
    std::cout << jobsDoneCounter << " jobs done" << std::endl;
}

I understand that overall complexity is aproximately O( J * C^R ), where: J = jobSize, C = cycleSize, R = recursionNumber What I struggle to comprehend is how much recursive calls happen on each step of base cycle - cycle from the very first call, where (in this example) recursionNumber = 4. Also I'm interesting in how to evaluate amount of doJob calls, a.k.a. jobCallCounter. Thank you!

Answer 1

You can find a recusive formula for that. If the time complexity for the problem with R recursion number and C cycle size (it is not an input to the recursive function) is denoted by T(R), we will have the following recursive formula:

T(R) = C* T(R-1) + 1

And for the initial case of the recursion T(0) = J. The 1 in the formula is for the checking codition in the code.

To solve the formula, you can expand it:

T(R) = C* (C * T(R-2) + 1) + 1 = C^2 T(R-2) + C +‌ 1 
     = C^R T(0) + C^{R-1} + ... + C + 1 = 
       C^R * J + C^{R-1} + ... + C + 1  = O(C^R * J)

Notice that as C and J are not changed their values during the recursion, we did not write the complexity function as T(R, C, J), to keep it simple for solving the recursion.