Mastery of Runtime Needed!

Since we have the recurrence, all that remains to do is solve it using the master method .

We can see from the given function that $a=2,b=2,c=1,f(n)\in O(n)$ . This falls under case 2, as we have $\log_b a = c$ . Since we can rewrite $O(n)$ as $O(n^1 \log^0 n)$ , it follows that the upper bound is $O(n^1 \log^{0+1} n)=O(n \log n)$ .

An algorithm with this recurrence that many may be familiar with is the merge sort, though others exist! See if you can come up with another similar algorithm.