Recurrence Relation working [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I am doing a data structures and algorithms paper in which recurrence relations are being taught.

The question is as follows:

From what I understand from this question, n will keep on being halved over and over again. So what you are left with is 1/32n^2 + 1/16n^2 + 1/8n^2 + 1/4n^2 + 1/2n^2 + n^2. All the fractions sum to 1. So you're left with n^2 +n^2 = 2n^2.

However this is not a possible solution.

Can somebody please help me understand how to calculate these recurrence relations correctly, or point me in the right direction because I am having a lot of trouble with this topic and any help with be greatly appreciated.

Thank you for your time.

Answer 1

You might want to look at the Master Theorem

In the wiki, a = 1, b = 2, c = 2, where T(n) = aT(n/b) + n^c

Case 3 applies, since 2 > 0 = log_2(1)

Thus, by the master theorem, T = Big-Theta(n^c) = Big_Theta(n^2).

Choice B has a n^2 term, so that should be your answer.