Recurrences in Divide-and-Conquer Algorithms | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 8.11 Free with a free account

Recurrences in Divide-and-Conquer Algorithms

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.11 · lesson 56 of 8710 min · free with a free account

← Solving Linear Recurrence RelationsNext lesson: Introduction to Generating Functions →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Running times that shrink by a factor, and the Master Theorem.

  • Write a divide-and-conquer recurrence
  • State the Master Theorem's 3 cases
  • Solve binary search and merge sort
  • Recognize where the theorem is silent

Transcript

Everything said in the video, section by section (1,501 words). Read along, or search it.

Binomial Probability, Recurrence Relations, and Generating Functions

Recurrences in Divide-and-Conquer Algorithms

This section covers a new shape of recurrence, one that comes from divide-and-conquer algorithms. Here, the running time on an input of size n, depends on the running time on a fraction of the input, like n over two. Not on a fixed offset, like n minus one. We'll solve these with the master theorem, and apply it to two of the most widely used algorithms in computing. Binary search, and merge sort.

The Opening Problem

Merge to Rebuild, Halve to Search

A ride-share platform stores its driver-location index as a sorted array of several million records. That way, a pickup request can be matched to the nearest driver in a fraction of a second. Two operations happen constantly on it. The array is rebuilt periodically, by merging freshly collected location batches into the existing order. And it's searched every time a new ride request needs to find its place in that order. Rebuilding by merging, and searching by halving, both have running times described by a recurrence where the input shrinks by a factor, not by a fixed amount.

Definition 8.11.1

T(n) = a T(n/b) + f(n)

A divide-and-conquer algorithm splits a problem into smaller subproblems of the same type, solves each recursively, and combines the results. Suppose it splits a problem of size n into a subproblems, each of size n over b. And it spends f of n time outside the recursive calls. Then its running time satisfies T of n equals a T of n over b, plus f of n. Here a is at least one, the number of subproblems. b is greater than one, the factor by which the size shrinks. And f of n is the work to divide the problem and combine the answers. Because the argument shrinks by a factor, not a fixed offset, the characteristic equation method from section eight point ten doesn't apply directly. A different tool is needed.

Example 8.11.1

Reading Off a, b and f(n)

Here's how to read off the parameters. Consider searching a sorted array. Compare the target with the middle element, which is constant work, then recurse into exactly one half. So a is one, since there's one recursive call. b is two, since the array halves. And f of n is constant, written theta of one. The recurrence is T of n equals T of n over two, plus a constant. That's binary search. The two parameters are easy to conflate. a controls how fast the number of active subproblems grows. b controls how fast the recursion reaches its base case.

Theorem 8.11.1

The Master Theorem

The master theorem compares f of n against one key quantity, the critical exponent c, which is the log base b of a. It's the growth rate the recursive calls alone would produce. Case one. If f of n grows slower than n to the c by a polynomial margin, then T of n is theta of n to the c. Case two. If f of n is exactly theta of n to the c, then T of n is theta of n to the c, times log n. Case three. If f of n grows faster than n to the c by a polynomial margin, and a regularity condition holds, then T of n is theta of f of n. This is the basic form, for f of n a polynomial, possibly with a log factor. The margin epsilon in cases one and three must be a fixed positive constant.

Reading the Cases

Which Part of the Tree Pays?

Each case has a direct reading. In case one, the combining work grows strictly slower than the baseline. So the recursive calls, the leaves of the tree, dominate the total. In case three, the combining work grows strictly faster. So the combining step at the root already costs more than everything below it. And case two is the boundary. Every level of the recursion does the same work, and there are about log n levels. For example, take T of n equals four T of n over two, plus n. The critical exponent is log base two of four, which is two. And n grows slower than n squared by a full power of n. That's case one. So T of n is theta of n squared. The four-way recursion outweighs the linear combining step.

Example 8.11.3

Binary Search

Now binary search. Its recurrence has a equal to one and b equal to two, so the critical exponent is log base two of one, which is zero. The combining work is constant, which is n to the zero. That matches the critical exponent exactly. So it's case two. Then T of n is theta of n to the zero times log n, which is theta of log n. Because a is one, only one subproblem is ever active. The recursion is a single chain, not a tree. For sixteen elements, it goes sixteen, eight, four, two, one. That's four comparisons, log base two of sixteen. It matches the direct argument. Each comparison discards half of the remaining candidates.

Example 8.11.4

Merge Sort

Merge sort splits an array into two halves, recursively sorts each, and then merges the two sorted halves in linear time, looking at each element once. So a is two, b is two, and f of n is linear. T of n equals two T of n over two, plus theta of n. The critical exponent is log base two of two, which is one. And linear combining work is n to the one, which matches exactly. So it's case two again. That gives T of n equals theta of n log n. That's the cost of rebuilding the ride-share index.

Figure 8.11.2

The Same Work at Every Level

This recursion tree verifies it directly, for eight elements. At the top, one call on eight elements does eight units of merging work. The next level has two calls on four elements each, still eight in total. Then four calls on two elements, again eight. And eight base cases, eight once more. Every level does the same total work, because it's split across twice as many subproblems, each half the size. There are about log n levels, each doing about n work. So the total is theta of n log n. That's exactly the level-by-level sum that case two packages into a single step.

The Code

Recursive Calls and the Combining Step

The code shows where each term comes from. The base case returns immediately for zero or one elements. The two recursive calls on the halves are the two T of n over two terms. And the final merge, which walks through every element once, is the linear combining step, f of n. Python's built-in sort uses an algorithm called Timsort, a hybrid of merge sort and insertion sort. It inherits the n log n worst case from its merge sort side.

Table 8.11.1

3 Cases Side by Side

Here are the three cases side by side. Case one, where the leaves dominate. Four T of n over two plus n gives n squared. Case two, balanced. Binary search gives log n, and merge sort gives n log n. Case three, where the root dominates. Two T of n over two plus n squared gives n squared. Notice that binary search and merge sort land in the same case, for different reasons. Binary search has a critical exponent of zero, matching constant work. Merge sort has one, matching linear work. So back to the ride-share index. Rebuilding it costs n log n, while each ride request's lookup costs only log n.

Where the Theorem Is Silent

A Gap Between the Cases

The master theorem doesn't cover everything. Consider T of n equals two T of n over two, plus n over log n. The critical exponent is one. And n over log n grows slower than n, but only by a logarithmic factor, not by any fixed power of n. So it isn't case one. It isn't exactly theta of n either, so it isn't case two. The theorem simply doesn't apply. Summing the recursion tree level by level gives theta of n log log n. That's strictly between n and n log n. More general tools, like direct recursion-tree summation or the Akra-Bazzi method, close gaps like this. The master theorem is a convenience for a common family of recurrences, not a universal solver.

Takeaways

Compare f(n) With the Critical Exponent

To summarize. A divide-and-conquer recurrence, T of n equals a T of n over b plus f of n, shrinks its argument by a factor. That makes it structurally different from the recurrences of sections eight point nine and eight point ten. The master theorem compares f of n with n to the critical exponent, log base b of a, and reads off the answer in one of three cases. Binary search is case two with exponent zero, giving log n. Merge sort is case two with exponent one, giving n log n. And when f of n sits within a log factor of n to the c, the theorem is silent. Here's something to think about. Before seeing the answer, which case seemed like the closest fit for two T of n over two, plus n over log n? Should the true answer be smaller or larger than n log n? And what's the difference between a theorem that's false outside its stated conditions, and one that's simply silent there?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Recurrences in Divide-and-Conquer Algorithms

What is a divide-and-conquer recurrence, and how do I read off a, b, and f(n)?
A divide-and-conquer recurrence has the form T(n) = aT(n/b) + f(n), where a \ge 1 is the number of subproblems, b > 1 is the factor the size shrinks by, and f(n) is the divide-and-combine work. Binary search has one call on half the array plus constant work, so a=1, b=2, f(n)=\Theta(1).
What are the three cases of the Master Theorem?
The Master Theorem compares f(n) with n^c, where c = \log_b a. Case 1: f(n) is polynomially smaller, so T(n)=\Theta(n^c). Case 2: f(n)=\Theta(n^c), so T(n)=\Theta(n^c \log n). Case 3: f(n) is polynomially larger and a regularity condition holds, so T(n)=\Theta(f(n)).
How do you solve the merge sort and binary search recurrences with the Master Theorem?
Both fall under case 2. Merge sort has T(n)=2T(n/2)+\Theta(n), so c=\log_2 2=1 and f(n)=\Theta(n) matches n^1, giving \Theta(n\log n). Binary search has T(n)=T(n/2)+\Theta(1), so c=\log_2 1=0 and constant work matches n^0, giving \Theta(\log n).
When does the Master Theorem not apply?
It does not apply when f(n) is close to n^c but differs only by a log factor, not a polynomial margin. For T(n)=2T(n/2)+n/\log n, c=1, and n/\log n is smaller than n but not by a power of n. That fits neither case 1 nor case 2. Summing the recursion tree gives \Theta(n\log\log n).

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →