question

EranMa-3548 avatar image
0 Votes"
EranMa-3548 asked XingyuZhao-MSFT edited

Recursion with 2 arguments inside a loop Time Complexity

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;
     }
dotnet-runtime
5 |1600 characters needed characters left characters exceeded

Up to 10 attachments (including images) can be used with a maximum of 3.0 MiB each and 30.0 MiB total.

1 Answer

XingyuZhao-MSFT avatar image
1 Vote"
XingyuZhao-MSFT answered XingyuZhao-MSFT edited

Hi @EranMa-3548 ,
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.


· 2
5 |1600 characters needed characters left characters exceeded

Up to 10 attachments (including images) can be used with a maximum of 3.0 MiB each and 30.0 MiB total.

Hi XingyuZhao-MSFT,

Thanks for your answer,
Can you elaborate how did you get to O(K power of 2)?




Regards,
Eran

0 Votes 0 ·

Hi @EranMa-3548 ,

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

In the worst case, the 'validsteps' is [1,2,3,...,N], and Max(validsteps) is N.
If K < N, when 'step' is N,'distance >= step' is false , so it is not the worst case for K.
If K = N,
For example, K=N=4, 'validsteps' is [1,2,3,4].
In the first execution of 'countpaths' method, it will execute countpaths(validsteps, 4- 1), so it contains the situation: K=3, 'validsteps' is [1,2,3,4] which is as same as K=N=3, 'validsteps' is [1,2,3], then is will execute countpaths(validsteps, 4- 2), also contains the situation: K=2, 'validsteps' is [1,2,3,4] which is as same as K=N=2, 'validsteps' is [1,2].
We can find that: K4 = K1 + K2 + k3 + 2(contains first and last execution of countpaths).
In a word: Kn = K1 + k2 + ... + K(n-1) + 2.
And: K(n+1) = K1 + k2 + ... + K(n-1) + Kn + 2
K(n+1) - Kn = Kn, so Kn is Equivalent Ratio Sequences, and K1 = 2.
So Kn = n power of 2.
If K > N,
For example, K=5,N=4, 'validsteps' is [1,2,3,4]'. the execution of countpaths is always less than 'validsteps' is [1,2,3,4,5]' which is K=N.
Finally, in the worst case,the time complexity is O( K power of 2) : O(2 k ).











1 Vote 1 ·