# Tag Info

## New answers tagged recursion

1

Let's start with the second function, fib2. If you count the number of operations, then you get only $O(n)$. So why is the running time given as $\Theta(n^2)$? The reason is that the Fibonacci numbers grow exponentially, and so addition can no longer be considered an $O(1)$ operation. The $n$-th Fibonacci number is $\Theta(n)$ bits in length, and this leads ...

1

"I find the non-recursive implementations using stacks are not easy to understand." One reason the complexity comes is due to "simulating" our own call-stack, which was done by compiler for the recursive method. The non-recursive variant may also include some optimization in addition to implementing what the recursive method does. "...

0

Your recursion can be written as: $$T(n) = aT(n/b) + f(n),$$ where $a=b=2$ and $f(n) = n \log^{-1} n$. Defining $c_{crit} = \log_b a = 1$ you can see that $f(n) = \Theta( n^{c_{crit}} \log^k n)$ for $k=-1$, therefore case 2b of the Master Theorem applies. The solution to the recurrence is therefore: $$T(n) = \Theta( n^{c_{crit}} \log \log n ) = \Theta( n \... 0 T(n)=3T(⌊n3⌋)+2nlogn By substitution method 2 Consider the recurrence$$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0,  which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$. The base case, $n=0$, is ...

1

A binary tree is a rooted tree where every internal node has at most two children. A recursion tree is a rooted tree which traces the execution of a recursive procedure. It need not be binary.

Top 50 recent answers are included