[Solved]: Can there exist a recurrence relation for "sequential search"?

Problem Detail: 

I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.

Asked By : Sameer Thigale

Answered By : David Richerby

Sure.

The cost of searching a list of length zero is zero; the worst-case cost of searching a list of length $n$ is one greater than the cost of searching a list of length $n-1$. So $$\begin{align*}T(0)&=0 \\ T(n)&=T(n-1)+1\,,\end{align*}$$ with solution being, as you'd expect, $T(n)=n$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32061

3.2K people like this

 Download Related Notes/Documents