Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

What is the Master Theorem?

Loading...

Algorithmic Toolbox

Université de Californie à San Diego

4.7 (5,462 évaluations) | 170K étudiants inscrits

Cours 1 de 6 dans Structures de données et algorithmes Spécialisation

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). Do you have technical problems? Write to us: coursera@hse.ru

Visualiser le programme de cours

Compétences que vous apprendrez

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Avis

4.7 (5,462 évaluations)

5 stars
4,060 ratings
4 stars
1,113 ratings
3 stars
197 ratings
2 stars
40 ratings
1 star
52 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

À partir de la leçon

Divide-and-Conquer

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

What is the Master Theorem?4:55

Proof of the Master Theorem9:45

Enseigné par

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcription

Here we're going to talk about the master theorem. We'll describe what the master theorem is and how to use it. And we'll reserve to the next video a proof. So we've had many occasions where we have had to write a recurrence relation for a divide and conquer problem. This is an example of one for binary search. We break a problem down into a problem half as big and we do a constant amount of work at each level. And this gives us a solution T(n) = O(log n). The problem is for each one of these we have to create a recurrence tree, figure out how much work is done at each level, sum up that work. That's a lot to do to solve each recurrence relation. Here's an example that we used for the polynomial multiplication. So we broke a problem into four sub-problems, each half the size, and did a linear amount of work. And the solution was T(n) = O(n squared). When we had the more efficient algorithm, where we had only three sub-problems instead of four, we then got a solution of O(n to the log base 2 of 3). Sometimes we break a problem into only two subproblems and there the solution is O(n log n). So, wouldn't it be nice if there was a way that we just had a formula to tell us what the solution is rather than having to create this recurrence tree each time? And that's what the Master Theorem basically does. So, the Master Theorem says if you have a recurrence relation T(n) equals a, some constant, times T( the ceiling of n divided by b) + a polynomial in n with degree d. And that ceiling, by the way, could just as well be a floor or not be there at all if n were a power of b. In any case, the a is a constant greater than 0. b is greater than 1 because we want to actually make sure the problem size gets smaller. And d is greater than equal to 0. Well, in that case, we have a solution for T of n. There are three sub cases. Case number 1, and all of these cases depend on the relationship between d, a, and b. In particular, is d greater than log base b of a? If so, the solution is just this polynomial in n, O(of n to the d). If d is exactly equal log base b of a, then the solution is big O of n to the d with an extra factor of log n. And finally, if d is less than log base b of a, then the solution is big O of n to the log base b of a. So let's look at some applications of this theorem. So here's one where we go back to the polynomial multiplication. Here a is 4, b is 2, and d is 1. Because O(n) is just O(n to the 1). And we look at the relationship between d, which is 1, and log base b of a, which is log base 2 of 4 or 2. Well clearly d is less than log base b of a, so we're in case three. Therefore T(n) = O(n to the log base b of a), or just O(n squared). If now we change the 4 to a 3, a is 3, b is 2, d is 1. Now d is still less than log base b of a because log base 2 of 3 is greater than 1, and so again we're in case three. T(n) equals O(n to the log base b of a), which equals O(n to the log base 2 of 3). If we reduce the 3 down to a 2 what happens? Well here, a is 2, b is 2, d is 1. Log base b of a is log base 2 of 2, which is just 1. So now d is equal log base b or a. We're in case two now. And so, T of n equals O(n log n). And now this shows an example also of case two. So this is the binary search example. A is 1, b is 2, d is 0. Well the log base two of one, log base b of a, is equal to zero. So d is equal to log base b of a. We're in case two, T(n) = O(n to the d log n), which is in the 0 log n, which is just O(log n). And a final example where we are actually in case one. So here a is 2, b is 2, and d is 2. So log base b of a is log base 2 of 2, which is one. So d is now greater than log base b of a. We are now in case one, T(n) equals O(n to the d), which is O(n squared). So what we've seen now is that we have this master theorem that allows us, for most recurrences, when you do a divide and conquer which fit into this general formula, allows us to easily figure out which case we are based on the relationships between a, b, and d. And then figure out the result quite quickly. In our next video we'll look at a proof of why the master theorem works.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. Tous droits réservés.

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales