120 views
2 2 votes

For $T(n,n)$, consider:

$T(x,c) = \Theta(x)$ for $c \leq 2$

$T(c,y) = \Theta(y)$ for $c \leq 2$

$T(x,y) = \Theta(x) + T(x,y/2)$
 

What is the asymptotic complexity of $T(n,n)$?

  1. $\Theta(\log n)$
     
  2. $\Theta(n)$
     
  3. $\Theta(n\log n)$
     
  4. $\Theta(n^2)$

1 Answer

0 0 votes
The correct answer is $\Theta(n \log n)$.

To see why, we rewrite the recurrence relation to avoid $\Theta$ notation as follows:

$$T(x, y)=c x+T(x, y / 2) .$$ We may then begin to replace $T(x, y / 2)$ with the recursive formula containing it:

$$T(x, y)=\underbrace{c x+c x+c x+\ldots+c x}_{\Theta(\log y) \text { times }} .$$ As a result, $T(x, y)$ is $\Theta(x \log y)$.

When we substitute $n$ for $x$ and $y$, we get that $T(n, n)$ is $\boxed{\Theta(n \log n)}$
Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
159
159 views
3 3 votes
1 1 answer
161
161 views
GO Classes asked Jul 29
161 views
Solve the recurrence:$T(n) = T(n-2) + \log n$Assume $T(n)$ is constant for small $n$.$O(\log n)$ $O(n)$ $O(n\log n)$ $O(n^2)$
2 2 votes
1 1 answer
136
136 views
GO Classes asked Jul 29
136 views
For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(x,y) = \Theta(x) + S(x,y/2)$$S(c,y) = \Theta(y)$ for $c \leq 2$$S(x,y) = \Theta(y) + T(x/2,y)$What is the asy...
2 2 votes
1 1 answer
136
136 views
GO Classes asked Jul 29
136 views
For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(c,y) = \Theta(y)$ for $c \leq 2$$T(x,y) = \Theta(x+y) + T(x/2,y/2)$What is the asymptotic complexity of $T(n,...