edited by
13,625 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

5 votes
5 votes

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

edited by
1 votes
1 votes

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.

edited by
0 votes
0 votes
as we can write this as :  T(n)= T(n-1) + n^0.5

so as per subtract and conquer equation;

a=1, b=1, f(n) = n^0.5

Now if f(n) = O(n^k)

lets check;

n^0.5 = O(n^0.5);  //take the value of K as small as possible to satisfy the condition

Now as a=1,

 so T(n) = O(n^k+1)

T(n) = O(n^0.5+1) = (n^1.5)

for T(m^2) = O(m^3)

therefore, answer B, because after multiplying m we get m^3.
Answer:

Related questions