1
$\begingroup$

I was analyzing the time complexity for recursive algorithms like merge sort, but when I came across that recurrence, [I think that equation is called a recurrence right?] I couldn't differentiate between a which mean the number of subproblems and b which in my slides it says is the factor by which n is divided by.

$\endgroup$
  • $\begingroup$ I suggest looking at examples which use this kind of recurrence to analyze the running time of an algorithm. $\endgroup$ – Yuval Filmus Jul 20 '18 at 10:26
  • $\begingroup$ @YuvalFilmus I don't want to analyze the algorithm just yet, I just want to understand what the variables 'a' and 'b' mean more clearly. $\endgroup$ – John Sall Jul 20 '18 at 11:18
  • $\begingroup$ The only way to understand it is to see some worked out examples. $\endgroup$ – Yuval Filmus Jul 20 '18 at 11:21
  • $\begingroup$ @YuvalFilmus This is a general formula for analyzing time complexity for recursive sorting algorithms. I hope we're not the only class in the world studying this method. It's strange you don't know about it $\endgroup$ – John Sall Jul 20 '18 at 11:43
  • $\begingroup$ You might be the only class in the world in which this formula is only studied "theoretically" without absolutely any examples. $\endgroup$ – Yuval Filmus Jul 20 '18 at 11:54
3
$\begingroup$

Here are three examples of algorithms with $b=2$ and $a=1,2,3$.

In all these examples, there is some small-scale cheating involved, which doesn't affect the asymptotic running time. I'll let the reader figure out where I'm cheating.

Binary search

In this algorithm, we are looking for an element $x$ in a sorted array $A$ of length $n$.

If $n = 1$, the problem is easy.

Otherwise, let $m$ be the index of the middle element:

  • If $x = A[m]$, we are done.
  • If $x < A[m]$, we recurse with the array $A[1],\ldots,A[m-1]$.
  • If $x > A[m]$, we recurse with the array $A[m+1],\ldots,A[n]$.

Every time we recurse, the size of the array decreases by a factor of 2. Therefore, the running time of binary search on inputs of length $n$ satisfies the following recurrence:

$T(n) = T(n/2) + O(1)$.

Here $a = 1$ and $b = 2$. The solution is $T(n) = O(\log n)$.

Merge sort

In this algorithm, we are sorting an array $A$ of length $n$.

If $n = 1$, the array is already sorted.

Otherwise, partition $A$ into two arrays $A_1,A_2$ of length $n/2$, sort each recursively, and then merge them in $O(n)$ time.

In contrast to binary search, in which we only recursed on one of the half-arrays, in merge sort we recurse on both. Therefore the appropriate recurrence is

$T(n) = 2T(n/2) + O(n)$.

Here $a = b = 2$. The solution is $T(n) = O(n\log n)$.

Karatsuba multiplication

In this algorithm, the goal is to multiply two $n$-bit integers $x,y$.

We first divide $x,y$ into two $n/2$-bit integers: $x = 2^{n/2} x_1 + x_2$, $y = 2^{n/2} y_1 + y_2$. We then proceed as follows:

  1. Compute $z_1 = x_1 y_1$.
  2. Compute $z_2 = x_2 y_2$.
  3. Compute $w = (x_1+x_2)(y_1+y_2)$.
  4. Return $2^n z_1 + 2^{n/2} (w - z_1 - z_2) + z_2$.

In steps 1,2,3, we are multiplying $n/2$-bit integers (more or less; in step 3 they are $(n/2+1)$-bit integers). The rest of the algorithm consists of addition and subtraction, which can be done in linear time. Therefore the appropriate recurrence for the running time of this algorithm is $$ T(n) = 3T(n/2) + O(n). $$ Here $a = 3$ and $b = 2$. The solution is $T(n) = O(n^{3/2})$, improving on the trivial $O(n^2)$ algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.