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 ...
answered Dec 31 '20 at 14:11
Yuval Filmus
241k2020 gold badges244244 silver badges426426 bronze badges
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.
answered Dec 22 '20 at 15:29
Yuval Filmus
241k2020 gold badges244244 silver badges426426 bronze badges
Top 50 recent answers are included
Related Tags
recursion × 475algorithms × 147
recurrence-relation × 72
algorithm-analysis × 71
runtime-analysis × 52
dynamic-programming × 51
time-complexity × 45
computability × 44
asymptotics × 30
trees × 25
master-theorem × 20
induction × 17
graphs × 15
binary-trees × 15
data-structures × 14
combinatorics × 13
turing-machines × 12
proof-techniques × 12
divide-and-conquer × 12
primitive-recursion × 12
complexity-theory × 11
functional-programming × 11
terminology × 10
programming-languages × 10
discrete-mathematics × 10