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
