Recursion with 2 arguments inside a loop Time Complexity

Question

I try to find the time complexity of this recursive function, how can I solve this?

lets assume the inputs are positive numbers, and valid steps is a unique list

ex:

validsteps = [1,2] distance = 3

validsteps = [1,2,3] distance = 4

'''C#

int countpaths(int[] validsteps, int distance)
    {
        if (distance == 0)
        {
            return 1;
        }

        int paths = 0; 

        foreach (int step in validsteps)
        {
            if (distance >= step)
            {
                paths += countpaths(validsteps, distance - step);
            }

        }

        return paths;
    }

Answer 1

Hi @EranMa ,
This method has no fixed time complexity.
Suppose the length of 'validsteps' is N, the value of 'distance' is k.
In the best case, the time complexity is O(1):

K <= Min(validsteps)  

For example:

validsteps = [2,3,4] distance = 1  

In the worst case，the time complexity is O( K power of 2) : O(2 k )

K = Max(validsteps) validsteps = [1,2,3,...,N]  

For example:

validsteps = [1,2,3,4] distance = 4  

Generally, the range of time complexity is between O(1) and O(K power of 2).
Hope it could be helpful.

Best Regards,
Xingyu Zhao
*
If the answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.