The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 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

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

+23 votes

Best answer

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

- $59$
- $75$
- non-integer
- $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 + \sum_i=1^{m-1} (2i+1). (i) $

$= m + \sum_i=1^{m-1} 2i^2 + i$

$= 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}.$]

+16 votes

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

Now we can apply master 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 master theorem.

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

0

@jatin saini How did you write this RR from given RR - **T(n)=T(n-1)+√n **

Did you put n=n-1 or subtract -1 from both sides?

+5 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(m^{2})

take m=2 so T(m^{2}) =T(4)

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

so ans is B

+1 vote

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.

0 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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 6k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,976 questions

47,609 answers

146,779 comments

62,342 users