Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
Diplômes
Certificats

Explorez l'intégralité de Coursera

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

What is the Master Theorem?

Loading...

Algorithmic Toolbox

Université de Californie à San Diego

4.7 (4,962 notes) | 160K é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 (4,962 notes)

5 stars
3,698 ratings
4 stars
1,005 ratings
3 stars
176 ratings
2 stars
36 ratings
1 star
47 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

AG

Feb 19, 2018

best course for clearing basics of algorithms as well as learning by doing and blow your mind by thinking hard from different prospectives to get desired solutions of programming assignments ...

À 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 propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

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

Télécharger dans l'App Store

Disponible sur Google Play

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

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