The correct answer is \Theta (n). To see why, 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 )+... This geometric sequence is bounded from above by 2c(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).
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). This is precisely the same recurrence relation as seen in above question, so it must have the same complexity \Theta (n).
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)=\underset{\Theta (\log y) \; times}{{\underbrace{cx+cx+cx+...+cx}}} 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 \Theta (n \log n).