edited by
13,626 views
52 votes
52 votes

Consider the following recurrence relation

$T(1)=1$

$T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$

The value of $T(m^2)$ for $m \geq 1$ is

  1. $\frac{m}{6}\left(21m-39\right)+4$
  2. $\frac{m}{6}\left(4m^2-3m+5\right)$
  3. $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$
  4. $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$
edited by

7 Answers

Best answer
72 votes
72 votes

$T(m^2) = T(m^2-1) + \left\lfloor\sqrt{(m^2)} \right\rfloor$

               $= T(m^2 - 2) + \left\lfloor\sqrt{(m^2 - 1)} \right\rfloor +\left\lfloor\sqrt{(m^2)} \right\rfloor$

               $= T(m^2 - 3) + \left\lfloor\sqrt{(m^2 - 2)} \right\rfloor + \left\lfloor\sqrt{(m^2 - 1)} \right\rfloor +\left\lfloor\sqrt{(m^2)} \right\rfloor$

               $\vdots$

               $= T(1) + \left\lfloor\sqrt{(2)} \right\rfloor + \left\lfloor\sqrt{(3)} \right\rfloor + \ldots + \left\lfloor\sqrt{(m^2)} \right\rfloor$

               $= 3 \times 1 + 5 \times 2 +  \ldots + \left(2m - 1\right) \times (m-1) +m $

(We are taking floor of square root of numbers, and between successive square roots number of numbers are in the series $3,5,7 \dots$ like $3$ numbers from $1..4$, $5$ numbers from $5-9$ and so on).

We can try out options here or solve as shown at end:

Put $m = 5$, $T(25)  = 3 \times 1 + 5 \times 2 + 7 \times 3 + 9 \times 4 + 5 = 75$

  1. $59$
  2. $75$
  3. non-integer
  4. $297.5$


So, answer must be B.


$T(m^2) = 3 \times 1 + 5 \times 2 +  \dots + \left(2m - 1\right) \times (m-1) +m$
              $= m + \displaystyle \sum_{i=1}^{m-1} \left[ (2i+1). (i) \right] $
              $= m + \displaystyle \sum_{i=1}^{m-1} \left[2i^2 + i\right]$
              $= m + \frac{(m-1) .m .(2m-1)}{3} + \frac{(m-1)m}{2}$
              $= \frac{m}{6} \left(6 + 4m^2 -2m -4m + 2 + 3m - 3\right)$
              $= \frac{m}{6} \left(4m^2 -3m + 5\right) $

  • Sum of the first $n$ natural numbers $=\frac{n. (n+1)}{2}.$ 
  • Sum of the squares of first $n$ natural numbers $ = \frac{n. (n+1). (2n+1)}{6}.$
edited by
67 votes
67 votes

we can write this recurrence as T(n)=T(n-1)+√n 

Now we can apply muster theorem for subtract and conquer 

here, a=1,b=1 f(n)=O(√n )

By case 2 of  subtract and conquer T(n)=O(n^1.5)

if we take n=m^2

T(m^2)=O(m^3),and which is tighter upper bound of  option B.

see below for subtract and conquer of muster theorem.

https://www.eecis.udel.edu/~saunders/notes/recurrence-relations.pdf

8 votes
8 votes

T(1)=1

T(2)=T(1)+⌊√2⌋=1+1=2

T(3)=T(2)+⌊√3⌋=2+1=3

T(4)=T(3)+⌊√4⌋=3+2=5

....... so on 

now find T(m2)

take m=2 so T(m2) =T(4)

now check options ,  only option B give value 5 which is equals to T(4)

so ans is B

6 votes
6 votes
One easy way to solve this is to try putting different 
values of m.

For example, we know T(1) = 1. If we put m = 1, only A
and B satisfy the result.

m = 2

T(2) = T(1) + 1 = 2
T(3) = T(2) + 1 = 3
T(4) = T(3) + 2 = 5

Both A & B produce 5

m = 3
T(9) = T(4) + 2*5 + 1 = 5 + 10 + 1 = 16
Both A & B produce 16

m = 4
T(16) = T(9) + 3*7 + 1 = 16 + 21 + 1 = 38
Only B produces 38, A produces 34 which doesn't match

Source:geeksforgeeks

Answer:

Related questions