GO Classes CS Test Series | Algorithms | Topic Wise Test 2 | Question: 12

Answer 1

The correct answer here is $\Theta(n)$. To see why, we want to first eliminate the mutually recursive recurrence relations. To do so, we will replace all references to the function $S(x, y)$ with the definition of $S(x, y)$. This yields the following recurrence relation for $T(x, y)$ :
$$
T(x, y)=\Theta(x)+\Theta(y / 2)+T(x / 2, y / 2)
$$
We can rewrite this to eliminate the constants and get the recurrence
$$
T(x, y)=\Theta(x+y)+T(x / 2, y / 2)
$$
We rewrite the recurrence relation to avoid $\Theta$ notation as follows:
$$
T(x, y)=c(x+y)+T(x / 2, y / 2) .
$$
We may then begin to replace $T(x / 2, y / 2)$ with the recursive formula containing it:
$$
T(x, y)=c(x+y)+c\left(\frac{x+y}{2}\right)+c\left(\frac{x+y}{4}\right)+c\left(\frac{x+y}{8}\right)+\ldots
$$
This geometric sequence is bounded from above by $2 c(x+y)$, and is obviously bounded from below by $c(x+y)$. Therefore, $T(x, y)$ is $\Theta(x+y)$, and so $T(n, n)$ is $\Theta(n)$

Comments

Nice Question

---

This geometric sequence is bounded from above by 2c(x+y), and is obviously bounded from below by c(x+y).

@Sachin Mittal 1 Sir, Can you please elaborate this line.

---

By solving the above decreasing GP series you will get the answer as 2c(x+y) and to get the bounded value you can remove the constant , now you will get c(x+y)

---

Bounded from above means in worst case what will it be ?

If we continue the above series to infinity, then we get $2c(x+y)$.

That means we will always have our answer $\leq 2c(x+y)$

 

Bounded from below means, minimum what we can get ?

If you see, the GP is decreasing, so we will get $c(x+y)$.

That means our desired answer is $\geq c(x+y)$

 

These are definitions of $\theta$. So, our answer lies somewhere between this upper bound and lower bound.

 

So, our desired answer will be : $c(x+y) \leq desired \leq 2c(x+y)$

In asymptotic manner, both $c(x+y)$ and $2c(x+y)$ are same.

So our desired answer will be:  $$T(x,y)=\theta(x+y)$$

$$T(n,n)=\theta(n+n)=\theta(n)$$

 

If there's any flaw in logic, please point it out !

Answer 2

 

this is answer

Answer 3

\[
\begin{aligned}
T(x,c) &= \Theta(x), && c\leq 2,\\
T(x,y) &= \Theta(x)+S(x,y/2),\\
S(c,y) &= \Theta(y), && c\leq 2,\\
S(x,y) &= \Theta(y)+T(x/2,y).
\end{aligned}
\]
$\text{We need to find \(T(n,n)\).}$
\[
T(x,y)=\Theta(x)+S(x,y/2)
\]
$\text{Using the definition of \(S\),}$
\[
S(x,y/2)=\Theta(y/2)+T(x/2,y/2)
\]
$\text{Therefore,}$
\[
T(x,y)
=
\Theta(x)+\Theta(y/2)+T(x/2,y/2)
\]
$\text{Again expanding \(T\),}$
\[
T(x/2,y/2)
=
\Theta(x/2)+S(x/2,y/4)
\]
$\text{Hence,}$
\[
T(x,y)
=
\Theta(x)+\Theta(y/2)
+\Theta(x/2)+S(x/2,y/4)
\]
$\text{Now,}$
\[
S(x/2,y/4)
=
\Theta(y/4)+T(x/4,y/4)
\]
$\text{Thus,}$
\[
T(x,y)
=
\Theta(x)+\Theta(y/2)
+\Theta(x/2)+\Theta(y/4)
+T(x/4,y/4)
\]
$\text{Continuing,}$
\[
T(x,y)
=
\Theta\left(
x+\frac{x}{2}+\frac{x}{4}+\cdots
\right)
+
\Theta\left(
\frac{y}{2}+\frac{y}{4}+\frac{y}{8}+\cdots
\right)
\]
$\text{Both are geometric series:}$
\[
x+\frac{x}{2}+\frac{x}{4}+\cdots=\Theta(x)
\]
$\text{and}$
\[
\frac{y}{2}+\frac{y}{4}+\frac{y}{8}+\cdots=\Theta(y)
\]
$\text{Therefore,}$
\[
T(x,y)=\Theta(x)+\Theta(y)
\]
\[
T(x,y)=\Theta(x+y)
\]
$\text{Putting \(x=n\) and \(y=n\),}$
\[
T(n,n)=\Theta(n+n)
\]
\[
\boxed{T(n,n)=\Theta(n)}
\]
$\text{Therefore, the correct option is}$
\[
\boxed{\text{B. }\Theta(n)}
\]

Answer 4

Option C is correct -