In this exercise, we're focusing on solving recurrences via recursion trees. It may help to visualize the

recurrence by drawing out the tree yourself.

Consider the following recurrence:

$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+O(n),T(1)=1$

For the purposes of analyzing the recurrence, we can replace the $O(n)$ term with $n.$ This changes the final

answer by a constant factor, which is irrelevant since we only care about the asymptotic complexity of the

recurrence. Thus, we can rewrite the recurrence as:

$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+n,T(1)=1$

Now let's analyze the Big $O$ of this recurrence.

For the $($Work Per Node, Number of Nodes$)$ column, the input must be formatted in order to be marked

correctly. Enter your input as a tuple. If there are different values for the work per node, enter as comma

separated tuples. Use ${?}^{{?}^{{?}^{?}}}$ for exponentiation. You may use a calculator here. WolframAlpha is useful for

displaying answers in fraction form instead of floating point. Complicated arithmetic will not appear on

exams.

The following are examples of valid inputs:

$(n,1)$

$(n^{{?}^{{?}^{?}}}\frac{2}{9},1),(n^{{?}^{{?}^{?}}}\frac{2}{4},2)$

$(2**\frac{n}{9},1)$

While these are invalid:

$n,1$ Not a tuple!

$((\frac{n}{3}{)}^{{?}^{{?}^{?}}}2,1),(\frac{1}{4}**n^{{?}^{{?}^{?}}}2,2)$ Incorrect formatting!

$(2\frac{n}{9},1)$ Incorrect formatting!

Can you try generalizing the total work for level $l?($use I for your input$)$

What pattern do you see?

Work per level is $a(n)$

What insight do we gain from this pattern?

The Big O sum is work per level $*$ number of levels

What is total number of levels in this tree? To enter logs in the form $lo{g}_b(a),$ enter your input as $log(a,b).$

And finally, let's put it all together! What is the overall running time of the recurrence?