GATE Overflow | Algorithms | Test 1 | Question: 29

Question

$$T(n) = \begin{cases} 4 & \quad  if \: \: n =1 \\ T(n-1) + 4  & \quad otherwise \end{cases}$$

Value of $T(1000)$ is ___

Answer 1

$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.$

Answer 2

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