in Algorithms
177 views
2 votes
2 votes
$$T(n) = \begin{cases} 4 & \quad  if \: \: n =1 \\ T(n-1) + 4  & \quad otherwise \end{cases}$$

Value of $T(1000)$ is ___
in Algorithms
by
177 views

2 Answers

5 votes
5 votes
Best answer
$T(n) = T(n-1) + 4 \\= T(n-2) + 8 \\=T(n-3) + 12 \\\dots\\=T(1) + (n-1)4\\=4+(n-1)4\\=4n.$

So, $T(1000) = 4000.$
selected by
by
2 votes
2 votes

The recurrence relation is similar to sequential search algoithm

So T(n) can be written as O(n)

=> T(n)=C*n(C is constant here)

T(1)=4 that means C=4

T(1000) would be 4*1000=4000

So Answer is 4000

Answer:

Related questions