New answers tagged

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 \...


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