Worst Case for staircase search

#1

How does the worst case for staircase search come out as N or (2N)?

#2

Hey @diganta_7777
Algorithm will work in time complexity of O(N) but it can take atmost 2*n steps .
i.e, i from 0 to n and j from n-1 to 0

Because either we go left or down
so We can atmax travel 2n steps

#3

Since there is only one loop is that the reason we make it N… because even in linear search we go through all elements(worst case) but since it has 2 loops, so it is N^2?

#4

No ita not the case
See
While(i<n^2)//here is also one loop but complexity is n^2

So in this ques in staircase approach
We start from top right i.e 1,n
And worst case will bw when element is at bottomleft i.e n,1
And inside our loop we are either moving down or moving left
So at max in above case we will go n down and n left
Hence 2n
Which makes complexity o(n)

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.