Need help in deriving complexity for Jumping Caterpillar Problem.

general
, ,
1

I have solved the Jumping Caterpillar problem on geeksforgeeks and I have gotten accepted. But I am not sure whats the complexity of my code.

Here is My Solution, can anyone help me in understanding what’s the time complexity of my code.

2

@arpit728 In reference to your code,

The j-loop takes N/a[i] steps.

The worst case shall occur when the elements are sorted in descending order in the array. Here the maximum value inside the input array is 100. Elements which are present multiple times will only enter the j-loop the first time. Elements which have a factor in the array at a position before them will not enter the j-loop.

The i-loop will run K times.
In the worst case, the inside loop will run a total of -

N/100+N/99+N/98+...N/1  times
= N*(1/100+1/99+1/98+...1/1)
=Nlog(100)

Thus the complexity of your code in the worst case is O(K+Nlog(max(a[i]))).

Hope this helped :slight_smile: