GATE CSE 2003 | Question: 35

Question

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

• A. $\frac{m}{6}\left(21m-39\right)+4$
• B. $\frac{m}{6}\left(4m^2-3m+5\right)$
• C. $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$
• D. $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$

Comments

We first find the time complexity of $T(n)$ and then substitute $n = m^2$. 
Thus, we obtain the time complexity of $T(m^2)$. 
From the given options, we choose the one whose time complexity matches this result.

$T(n) = \frac{2}{3} n^{3/2}$,
$T(m^2)=\frac{2}{3}\left(m^{2}\right)^{3/2}=\frac{2}{3}m^{3}$ 
$T(m^2)$ $=$ $O(m^3)$ 

From Options Option B matches.  

     

---

Any Reference for this method

---

How did you solved the recurrence for T(n) can you explain?

 

Answer 1

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

• A. $59$
• B. $75$
• C. non-integer
• D. $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}.$

Comments

https://math.stackexchange.com/a/1242332/545704

---

Generally when solving recurrences (esp for time complexity) we ignore the floors and ceilings. Trust the GATE paper setting professors to exploit this habit by making sure the floor actually matters when solving a recurrence...

Really nice solution.

---

$T(1) + \left \lfloor\sqrt{2} \right \rfloor + \left \lfloor\sqrt{3} \right \rfloor + \left \lfloor\sqrt{4} \right \rfloor + \left \lfloor\sqrt{5} \right \rfloor + \left \lfloor\sqrt{6} \right \rfloor + \left \lfloor\sqrt{7} \right \rfloor +  \left \lfloor\sqrt{8} \right \rfloor +........ $

= 1 + 1 + 1 + 2 + 2 + 2 + 2 +2 +...

= 3 *1 + 5 *2 +.....

Answer 2

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

Comments

Best Answer

---

@Rish9799 yes you are correct. 

---

Note that subtract and conquer muster theorem is not a standard solution. The source cited in above answer mistakenly assumes f(n-ib) to be O(n) in the proof which I think is the reason for incorrect solutions provided by the so called "muster theorem".

Answer 3

All options have different complexities. i.e.

$A) \:O(m^2) \:\: B) \:O(m^3)\:\: C) \: O(m^{3.5}) \: \:D) \: O(m^4)$

So, We can get time complexity T(n) from the recurrence relation and match with options. We ignore floor for worst case time complexity calculation.

$T(n+1) = T(n) + \sqrt{n+1}$

$Put\: n +1 = m^2$

$T(m^2) = T(m^2 - 1) + m$

$Put\: m^2 = p \:\: -(2)$

$T(p) = T(p - 1) + \sqrt{p} \:\:\: -(1)$

Here we have 2 methods to solve:

1st Method:

Using Subtract and Conquer(link) you will get :

$T(p) = O( p^{1.5+1} ) = O(p^{2.5}) = O(p\sqrt{p})$

$Put\: p = m^2 \:\: (using \: (2))$

$T(m^{2}) = O(m^{2} * m) = O(m^{3})$

$So\: B) \: is\: answer.$

2nd Method:

The recurrence relation (1) is sum of first p square root numbers.

Although we have floor of square root of numbers we are finding worst case time complexity so floor won't matter here.

$i.e. \: T(p) = \sqrt{1} + \sqrt{2} + ... + \sqrt{p}$

By Ramanujan’s formula for sum of the square roots of first n natural numbers (link for proof):

$T(p) = \frac{2}{3} . (\:(p-2) \sqrt{p+1} - 2\sqrt{2}) + 1$

$\therefore\: T(p) = O(p\sqrt{p})$

$Put\: p = m^2 \:\: (using \: (2))$

$T(m^{2}) = O(m^{2} * m) = O(m^{3})$

$So\: B) \: is\: answer.$

Comments

could u plz elaborate on how u had found the time complexities for the given 4 options

---

but its only gigivn uppper bound ri8?

---

Small Correction :
$T(p)=O(p^{0.5+1})=O(p^{1.5})=O(p\sqrt{p})$

Answer 4

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(m²)

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

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

so ans is B

Comments

@Gate Ranker18

Nopes , even option A will be also true , if u will do like this. So u can not say like this .

---

Yes exactly option A is also matching when m=2 and for m=3 also.

---

@Quantum City plz help 

---

Option A also matching and we can't go with option elimination also as its taking lot of time

Answer 5

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

Comments

Here's how you can sum floor of square roots of n natual numbers.

Check out the link below 

https://math.stackexchange.com/questions/1241864/sum-of-square-roots-formula

One can also substitute value and get the answer but the explanation is interesting so I thought I should mention it.

Answer 6

Using Integration bounds technique we can get approximate answer.

Integration bound method is explained in detail here(page 11, theorem 9.3.1). 

$T(n) = T(n-1) + \left \lfloor \sqrt{n} \right \rfloor , n > 1$

Unrolling it gives,

$T_n = \sum_{k = 1}^{n} \left \lfloor \sqrt{k} \right \rfloor$

But, because $k - \left \lfloor k \right \rfloor < 1$

$\sum_{k = 1}^{n} \sqrt{k} - n \le T_n \le \sum_{k = 1}^{n} \sqrt{k}$

So, Let's find $S_n = \sum_{k = 1}^{n} \sqrt{k}$

Integration bound theorem: if $f$ is non decreasing function, $S = \sum_{k = 1}^{n} f(k)$ and $I = \int_{1}^{n} f(x) * dx$ then $I + f(1) \le S \le I + f(n)$.

$\frac{2}{3}*n^{\frac{3}{2}} - \frac{2}{3} + 1 \le S_n \le \frac{2}{3}*n^{\frac{3}{2}} - \frac{2}{3} + \sqrt{n}$

$\frac{2}{3}*n^{\frac{3}{2}} + \frac{1}{3} - n \le T_n \le \frac{2}{3}*n^{\frac{3}{2}} - \frac{2}{3} + \sqrt{n}$

Taking $n = m^2$

$\frac{2}{3}*m^3 - m^2  + \frac{1}{3} \le T_{m^2} \le \frac{2}{3}*m^3 - \frac{2}{3} + m$

Closet match is B.

Comments

solved in same way