This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->
MIT Algorithms

I just finished watching the last lecture of MIT's "Introduction to Algorithms" course. Having a great passion for all aspects of computing, I decided to share everything I learned with you! This is the first post in an article series about this course.

As I wrote earlier, I am very serious about watching video lectures. If they are math-intensive, I usually take notes as if I were in the classroom. Lectures in this course were exactly like that -- logarithms, big-o's, thetas, expectations, and all the other math guys fighting with each other on the blackboards.

There are totally 23 video lectures, each around 1 hour 20 minutes long. I will be posting about 2 - 3 lectures at a time which will result in approximately 10 blog posts. Each post will contain annotated lecture, along with embedded video of the lecture and a time-stamped list of topics covered in the lecture. I will also post the notes I took myself as I watched the lectures (actually, I just bought a scanner (Canon CanonScan 4400F) just for this purpose!)

Understanding and designing effective algorithms is a very important skill for a top-notch programmer. You can still do good without knowing much about algorithms, but knowing them makes you superior. There are two kinds of people, those who can design effective algorithms and those who don't. ;)

Let's start with Lecture 1 of this course.

Lecture 1: Analysis of Algorithms

The first lecture is given by the famous professor Charles E. Leiserson. He is the L in CLRS. If that doesn't ring you a bell - it's one of the most popular books on algorithms!

He starts the lecture by explaining what this course and algorithms will be all about. He says that this course will be about "Analysis of Algorithms" and states: "Analysis of algorithms is the theoretical study of computer program performance and resource usage".

Designing great software is not just about performance. Charles presents a list of 12 things that can be more important than performance. Just for comparison with algorithms guru, what do you think can be more important than performance?

Here is the list of things more important than performance that Charles presented:

  • modularity,
  • correctness,
  • maintainability,
  • security,
  • functionality,
  • robustness,
  • user-friendliness,
  • programmer's time,
  • simplicity,
  • extensibility,
  • reliability, and
  • scalability.

He also asks "Why study algorithms and performance at all?". He and students answer:

  • Sometimes performance is correlated with user-friendliness.
  • Performance draws line between feasible and unfeasible.
  • Algorithms give language for talking about program behavior.
  • Performance can be used to "pay" for other things, such as security, features and user-friendliness.

The lecture continues with the definition of the Sorting Problem - given a sequence (a1, a2, ..., an) of numbers, permute them in such a way that a1 <= a2 <= ... <= an.

There are various algorithms to solve this problem. Two algorithms are presented to solve this problems - one of them is Insertion Sort and the other is Merge Sort.

Running time of these algorithms is analyzed by introducing Asymptotic Analysis and Recursion Trees.

Here is the whole lecture:

Topics covered in lecture 1:

  • [17:15] Main topic of the course - Analysis of algorithms.
  • [19:00] What's more important than performance?
  • [22:03] Why study algorithms and performance?
  • [27:45] The sorting problem.
  • [29:30] Insertion sort algorithm
  • [34:30] Example of Insertion sort.
  • [36:25] Running time of algorithms.
  • [39:39] Definition of worst-case, average-case and best-case types of analysis.
  • [46:50] How to analyze the Insertion sort's worst-case running time?
  • [49:28] BIG IDEA - Asymptotic analysis.
  • [50:49] Asymptotic notation - theta notation.
  • [57:14] Insertion sort analysis.
  • [01:02:42] Is Insertion sort fast?
  • [01:03:40] Merge sort algorithm.
  • [01:05:25] Example of Merge subroutine of Merge sort.
  • [01:08:15] Analysis of Merge sort's running time.
  • [01:10:55] Recurrence equation for Merge sort.
  • [01:13:15] Recursion tree solution of the Merge sort's recurrence equation.

Lecture 1 notes:

MIT Algorithms Lecture 1 Notes Thumbnail. Page 1 of 2.
Lecture 1, page 1 of 2.

MIT Algorithms Lecture 1 Notes Thumbnail. Page 2 of 2.
Lecture 1, page 2 of 2.

Lecture 2: Asymptotic Notation

Lecture 2, on the other hand, is given by genius professor Erik Demaine. He is the youngest professor in the history of the MIT! He became professor at MIT at 20! Wow!

This lecture is all about mathematical notation (Asymptotic Notation) used in the analysis of algorithms. It's the big-o notation, big omega notation, theta notation, small-o and small-omega notation.

The second half of the lecture is devoted to solving recurrence equations. Three methods are presented:

  • Substitution method,
  • Recursion-tree method, and
  • The Master method.

Here is the whole lecture:

Topics covered in lecture 2:

  • [01:25] Big-o (upper bounds) notation.
  • [03:58] Set definition of big-o notation.
  • [05:25] The meaning of O(h(n)) in notation f(n) = g(n) + O(h(n)).
  • [10:20] Big-omega (lower bounds) notation.
  • [11:40] Analogies of O, Ω and Θ to comparison operations of real numbers.
  • [12:28] Theta (tight bounds) notation.
  • [13:40] Small-o and small-omega notation.
  • [17:03] Solving recurrences: substitution method.
  • [37:56] Recursion-tree method.
  • [49:00] The Master method.
  • [01:02:00] Proof sketch of the Master method.

Lecture 2 notes:

MIT Algorithms Lecture 2 Notes Thumbnail. Page 1 of 2.
Lecture 2, page 1 of 2.

MIT Algorithms Lecture 2 Notes Thumbnail. Page 2 of 2.
Lecture 2, page 2 of 2.

MIT Algorithms Lecture 2 Notes Thumbnail. Master's Theorem.
Lecture 2. Sketch of Master's theorem proof.

Have fun absorbing all this information! Until next post!

Ps. It turned out that the lectures were not available anywhere but from MIT's OCW website. I found that they were released under CC license, which allowed me to upload them to Google Video, so I can embed them in the posts!

Pps. the lectures are taught from the CLRS book (also called "Introduction to Algorithms"):

This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->


James Permalink
August 20, 2008, 04:13

Is it just me, or are both videos lecture #2?

August 20, 2008, 04:46

Oops, James, you are right. I have made some kind of a mistake and uploaded the same video twice or something.

Fixing it now.

Danno Permalink
August 20, 2008, 05:00

Thanks for the transcodes Peter. I can hardly believe that MIT decided to use Real for these... unless it's just a container for the encode.

August 20, 2008, 05:08

Danno, it's true. MIT used Real for those.

I took the opportunity to upload them to Google Video, as they were released under CC license. I am uploading a video at a time as I write more posts.

Matt Permalink
August 20, 2008, 05:31

So, I've taken and taught this class (as a TA, that is), and the one thing I need to emphasize to anyone that wants to really go through this class through OCW... the bulk of the learning in this class is in the problem sets. They are hard. They are very hard. They normally took a good 8+ hours each for a solid group of 2-4 MIT CS students.

I haven't looked at the OCW versions, but don't waste the material by looking at the solutions before you have a good struggle with them. As a student, and as a teacher, they were by far the most important aspect of the class.

Brennan Permalink
August 20, 2008, 06:32

As someone who has also taken the class, I second what Matt said. Most of the learning will happen from the problem sets. But also as Matt said, the problem sets usually are worked on in groups, so if you have a friend who's interested as well, it would probably make your life a lot easier to have someone to bounce ideas off of.

August 20, 2008, 06:48

Hey, thanks for the share! Really enjoying this. It's great to see someone's notes as they show how another person intakes the information. neat notes too =P

August 20, 2008, 06:49

Concur w/Matt + Brennan.

Erek Permalink
August 20, 2008, 07:51

As another person who has taken the class, I never worked in a group during this class.

In fact, in my career at MIT I've only done 1 pset in a group. Groups can be good, but for most people I think they impede learning.

August 20, 2008, 08:47

here you can find many of the algorithms of the book coded in Python.

August 20, 2008, 10:54


Thanks for this and for converting the videos for YouTube. Makes life much easier.

August 20, 2008, 11:38

oh, you got coloured crayons :)
nice work :)

August 20, 2008, 12:35

Wow, thanks, this reminds me of another, shorter, Great Course available from Stanford which I'd been meaning to post about for ages. The professor covers "the future of the internet" with a true expert's precision. He makes clear subtle economic points and lays out who really has the upper hand in the internet economy, why many communications acquisitions work or are bungled, etc. Though not pure CS, certainly relevant to the same crowd with a similar intensity to this MIT algorithms course.

sml Permalink
August 20, 2008, 13:34

In the bulleted list of items, I'm assuming item #5 "functionaly" should be something other than "functionaly" like functionality?

Thanks for posting the notes and reviews. It will motivate me to spend some time going through the videos.

August 20, 2008, 14:43

babul, you are welcome :)

spx2, it's not crayons, it's soft color pencils :)

sml, you are right, it's "functionality". I am correcting that mistake now. Nice to hear that it will motivate you :)

I also agree with everyone who said that you should also solve a lot of problems, psets or at least quizzes!

August 21, 2008, 03:19

This is no less than the 3rd time I've come upon your site and taken the tour of a subject matter through the provided lens. I distinctly remember following a Python thread and a thread re: one videos from one of the H/P/A/V'cons, and each subject has been extremely well presented ...

Thank you for taking the time to share your notes and doing a write-up, I watched the video first and then read your write-up as a reinforcement. Good stuff.


August 21, 2008, 04:20

This is a great initiative- building communities of learners in each subject. Let us hope more listeners come up with course blogs like you. You may also take notice of developments outside of MIT OCW. For example visit:

Where you will suites of about 40 hours of recorded lectures in each course in about 60 courses (and increasing) for the undergraduate engineering subjects posted by the IITs in India. Meanwhile Wikipedia is trying to establish a Wikiversity. Best wishes.

DeepTrouble Permalink
August 21, 2008, 04:47


I am just going through these lectures myself (haven't finished them yet, though). My approach is a little bit different.

Aside from traditional lecture notes, I put the information in a spaced repetition system like Mnemosyne (there are a few others but this one works great for me).

This thing tells me exactly when to review my notes. I make the flashcards on the fly as I watch the lectures.

The advantage is that I can take for example a longer break from watching the lectures (if for example you don't have time) and as long as you do your repetitions, you will be able to go back right where you left off.

I always had trouble previously because after watching 2-3 lectures, I had to interrupt for some reason or another and then start over from the beginning to make sure I remember everything.

You also have the added bonus of always keeping 90% of the knowledge in the lecture inside your head.

August 21, 2008, 07:28

Could you host the videos on anything else? Google Video is often unavailable in China. For example I cannot watch the videos now. Youtube would be better.

August 22, 2008, 18:28

Looks interesting, but I give up as soon as I hear a lecturer speaking verbatim while he is writing on a blackboard "Theerrre ... aarrre ...." One should not be allowed in front of students with this crap.

August 22, 2008, 20:03

Peter: Nice site and thanks for being sure to mention our CC license. Our videos are also available through YouTube with embedding enabled, which might save you some trouble. They are also available through iTunes U for download.


Steve Carson
MIT OpenCourseWare

Daniel Permalink
August 22, 2008, 23:45


Only the audio (for this course) seems to be available via iTunes U. To be honest, I don't find just the audio very useful for a course like this. I would very much appreciate it if the video lectures were uploaded to iTunes U!

August 23, 2008, 18:34

Like one of the comments states: Doing the psets and spending like the 8 hours on it is how you get the most out of this class. I don't know if they post the take-home test too, but that's definitely challenging.

Michael Permalink
August 25, 2008, 06:00

Argh! RealVideo is the most frustrating format I've ever had to deal with.

How are you converting these?

August 25, 2008, 13:59


I used Avisynth + Virtualdub + Realtime Alternative.

First I installed Realtime Alternative, then Virtualdub, and then Avisynth.

Then I created this Avisynth script for each realtime video:

file = "ocw-6.046-31oct2005-220k.rm"


I named each script like ocw01.avs, ocw02.avs, ... ocw23.avs.

Then I loaded each script one by one in Virtualdub and chose Audio -> Full Processing Mode, and selected Audio -> Compression to be mp3 at 16kbit/s.
The same for Video. Go to Video, select Full Processing Mode. Then select compression to be DivX at 230kbit/s.

Then File -> Save as AVI and save the video to ocw01.avi, then load the next .avs and save to ocw02.avi, etc.

This was time consuming but I was unable to automate it with ffmpeg.

huma Permalink
August 25, 2008, 20:42

thadk: hey, where did your article and the blog go?

"The requested URL /wp/2008/08/20/the-future-of-the-internet-review-of-stanford-itunesu-course/ was not found on this server."

huma Permalink
August 25, 2008, 20:49

btw, thanks peter :) great job. it's a good addition to autodidactism :)

August 26, 2008, 01:49

very interesting!
thank you :)

Peteris Ledins Permalink
October 25, 2008, 05:00

I guess I'm not following the second lecture:
1/2 * c n^3 - n == -.5 if n=c=1...
which is lt 0...

giogio Permalink
February 10, 2009, 15:43

please someone answer the follow question

how can i prove that we can create a minimum spanning tree with Prim,Kruskals algorithms in the case that the weight of a tree w(T) is the largest (maximum) of the weights of the edges e


Amit Gupta Permalink
February 20, 2009, 18:49

Dude can you please tell me where i can get all the video lectures. Google video doesn't have all of them and its such a pain in the ass that i cant find all the lectures on one website. Also the sites that claim to have the lectures keep crashing on my browsers !!

February 24, 2009, 21:33

Peter, Fantastic Job!

I have just started going through the lectures. Would you recommend a good way to download these video to watch offline?


moo Permalink
March 19, 2009, 08:52


Is there some compact material about that math requirement he mention?
I remember something from my study time, but can't really follow all that math stuff that are in this course.

April 05, 2009, 10:47

Most of the lecture videos can be found on MIT page.

And thanks kurumin for the informative post.

EPerez Permalink
May 06, 2009, 19:31

Awesome, just what I was looking for! In combination with school this is an excellent tutorial!

Richard Permalink
May 06, 2009, 22:30

Are the problem sets (and, ideally, answers) available anywhere online? I think following along with the lectures is great, but being able to look at the problem sets would be even better.

Ingororano Permalink
May 29, 2009, 14:18

very nice work, every bobdy have to be
interested, continue and improve.thx

Amit Permalink
September 19, 2009, 07:09

Brilliant work fellows, it is really helpful for students like us from other institutes all over the world.

September 19, 2009, 07:12

This is a scholar from National Institute of Technology, Srinagar, India. These web realeases of MIT lectures have been quite helpful. Great work over thr guys!

Arslan Asif Permalink
October 13, 2009, 16:03

Any one tell me what will be the upper bound of following recurrence.

T(n)= T(n-1)+n^2.

Arslan Asif Permalink
October 13, 2009, 16:05

Sorry, its
T(n) = 2T(n-1)+n^2

October 16, 2009, 01:27

Arslan, it's exponential O(2^n).

At root level you have work n^2, at 1st level 2(n-1)^2, at 2nd level 4(n-2)^2, ..., at i'th level 2^i(n-i)^2.

FrankC Permalink
November 02, 2009, 01:59

Peter: "fantastic work"; and "thank you very much"; How do I grow the new lobe on my brain to hold this :-)

November 12, 2009, 09:02

As usual, I loved this post too. This is a nice to have list of algorithms related lectures. This one goes straight to my delicious account.

sultannur Permalink
November 19, 2009, 00:00

i have to thank u cos these notes and videos helped me so much for understanding the logic. i studied wth these videos and notes and find all my questions answers about these topcis. they re really reallyy helpful and good explained. thanks to all =)

Arunan Permalink
February 04, 2010, 05:42

Looks like Alexander Calder's sculptures on the cover of the book. I've had the book for undergrad algos courses, but only now am I noticing this after my arts course. Interesting .. Very Interesting.

christina Permalink
February 09, 2010, 11:47


I'm studying for tomorrow's exam in Algorithms & Complexity (which I will probably fail as I never actually followed the course) and I stumbled on your blog in a frenzied attempt to get a better grip on the Master Theorem.

I am in love with your blog(and the mit course videos), downloaded all the course's problem sets for a bit of self summer schooling :P. It's resources like this that make the internet so gr8 :))))

super super thank you =D

March 24, 2010, 11:45


Videos are not available, please post working links.

Waiting for your reply.


Vaishali Permalink
March 30, 2010, 08:58

For studying analysis of algorithms following links are also helpful:

April 18, 2010, 11:33

There us no audio in these videos while
playing in vlc
Plz suggest the recommended player

fffffffff Permalink
May 29, 2010, 00:11

mplayer works fine, Shrish.

Ritu Shrivastava Permalink
May 31, 2010, 04:53

I liked your notes very much. It helped me a lot. Thanx.

Abhijeet Singh Permalink
June 20, 2010, 21:49

cn anyone tell me in l1 y the height of tree is logn??
cant figure it it too obvious??

Rahul Permalink
July 14, 2010, 10:19

well. if tree is complete binary tree, no of nodes in tree can be found using formula n = 2 pow h, where h is the height to tree.if u take log on both sides it comes out to log(n) = h log(2).
log(n) = h log(2) of log base 2
h = log(n).

but this is valid in case of complete binary tree.
i hope this solve your query.

October 04, 2010, 18:31

Very good summary and thanks for the notes. They are really helpful. I`m looking forward to more.

suvarna Permalink
October 13, 2010, 08:27

Aside from traditional lecture notes, I put the information in a spaced repetition system like Mnemosyne (there are a few others but this one works great for me).

This thing tells me exactly when to review my notes. I make the flashcards on the fly as I watch the lectures.

The advantage is that I can take for example a longer break from watching the lectures (if for example you don't have time) and as long as you do your repetitions, you will be able to go back right where you left off.

perfwill Permalink
October 29, 2010, 13:30

Do you think that a 10th grader in high school can understand all the stuff of this whole course?

December 20, 2010, 15:55

Well, why don't you give it a try? I believe an overall exposure to basic math, algebra and stuff coupled with a lot of interest to learn is more than enough I guess :)

Any ways, to @pkrumins: I started learning this book myself at home after work, with these lectures, I'm happy am not alone!

June 02, 2011, 00:28

This is awesome. These video helped me a lot during my data structure classes. I actually learned more on this website than in class :-)

Georges Permalink
October 16, 2011, 12:39

Thank you. I will do all the courses.

kushal bansal Permalink
December 03, 2011, 04:02

the content of the blog was great but it would be highly appreciated if it also contains some material related to c proghramming tips
thanks and regards!
kushal bansal

Caruli Permalink
December 29, 2011, 20:42

Well done Peter,

What are the requirements for the second lecture?
I got lost straight away.

December 29, 2011, 21:39

Discrete math, calculus, math logic.

Anand Permalink
January 17, 2012, 07:08

@Peter : well done buddy ,,

I am very much afraid if i can't understand the lectures,, fingers crossed

Birol Permalink
February 14, 2012, 16:34

What is currently the best place to download the lecture slides and/or videos?

Birol Permalink
February 14, 2012, 16:35

Would appreciate if someone can mail the best place to download the lecture slides and/or videos.


Birol Permalink
February 14, 2012, 16:37

Pls mail to birolayg at gmail dot com.

Sorry it took me three comments to get it right.

nour Permalink
February 19, 2012, 06:33

I am from syria ,I speak arabic , I watch lecture 1&2 ,I did not understand "substitution method" ,can you explain it in simple way ,with more examples. thank you.

February 27, 2012, 02:39

Hi nour,

There are two steps to the method.
1. Guess the solution
2. Prove the solution by induction

For example, we try to get the upper bound of T(n) = T(n/2) + 1 (this is the recurrence relation for binary search)

My guess is o(lgn) so our guess should look like T(n) <= clgn for some c and n > N.

Then we prove the guess by induction.

We assume that T(k) <= clgk holds for k < n.
T(n) = T(n/2) + 1
<= clg(n/2) + 1 (note: we invoke the assumption here)
= clgn - clg2 + 1
= clgn - (clg2 - 1) (note: we rearrange them to the form desired - residual)
<= clgn when c >= 1/(lg2)


February 27, 2012, 02:52

hey peter,

thanks for your notes! I'm reading it for my test this week. =)


shyam sunder Permalink
March 12, 2012, 05:59

Hey i am looking for someone who can help me solve the problems in Analysis of Algorithms Second Edition
Author- Jeffrey J.Mc.Connell

JohnB Permalink
March 20, 2012, 06:07

Just watched the 1st of the series this morning.
Recv'd BSc (TESC-1980) and have been professional since-
am expecting this to be a great review.
Also wanted to Thank the SysOp for this board -
I know already that communication is the key when one get's stuck.

JohnB Permalink
March 20, 2012, 06:24

I found this helpful / useful to Charles first lecture. BTW I did not agree that Bells & Whistles ,
( user friendliness & functionality) takes precedence over Performance.

Meaning, if it doesn't have good to outstanding "Performance" , then it'll never fly. Either the director won't let it out-the-door, or if it does, by fluke, get released, then no-one will buy it.

Point in fact, the Radio Shack Trash-80, sorry, meant to say TRS-80, had all the good points of friendliness and B.A.S.I.C language, but just didn't have any performance! If the programmer / analyst doesn't put Performance as Job #1, then the competition will !, no-matter how fun or exciting, salable, modular, extendable or secure yours is.

JohnB Permalink
March 20, 2012, 07:11

This, is what it was that I found to be useful to Charles' First Lecture.

Raghu Permalink
November 01, 2012, 16:15

Hi Peter Krumins, Can you please give me access to the videos.(

November 05, 2012, 06:10

Your handwriting is horrible, but otherwise it is very useful. So, thanks a lot.

fealolz Permalink
November 23, 2012, 18:08

Hi. I can't access the videos at all. Getting the Errormsg: "This video is privat". How to fix that?

suresh Permalink
January 11, 2013, 06:39

OOoops! Can i Download this vidio???

Raj Permalink
January 19, 2013, 03:14

I am not able to access the videos. I am seeing " The video is private". How can I access them for quick review for myself.

Watsh Rajneesh Permalink
February 09, 2013, 02:33

Same here .. i cannot access the video - says the video is private.

prasad Permalink
March 05, 2013, 05:55

Someone please give me access to these videos...
I can't see it - says the video is private.

Heather Permalink
March 24, 2013, 20:18

Dear poster,
Can you please make the videos accessible to us online or YouTube...or give us some type of key/password pretty please?
Thanks a lot!

Wizkid Permalink
March 28, 2013, 23:59

I think the MIT course - including lecture videos and other materials, is available at:
the 'download course materials' page also lists other links for videos...

Wizkid Permalink
March 29, 2013, 00:03

Actually this link is there in the original post only - just noticed !
Thanks Peter for all the notes and for sharing...

Doug Permalink
March 29, 2013, 06:11

There are two more books :

Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach by Lin Quan.

Algorithms Unlocked by Cormen

Anon Permalink
April 18, 2013, 16:44

Hey Doug,
Do you have the pdf of these books?

Kunjal Davawala Permalink
October 22, 2013, 21:57


I would love to learn from this videos. but I can't access them may be the link is broken or something. Please tell me how to access it.

Tài Permalink
December 02, 2013, 12:36

I cannot access your videos. Maybe links are broken

araybold Permalink
February 07, 2014, 19:42

Of the list of things more important than performance, I think only correctness always belongs there (especially given that adequate - not best possible - performance is an aspect of correctness, and similarly for security.) The importance of everything else is conditional, and the priorities negotiable.

sare Permalink
February 28, 2014, 08:29

thanks a lot.

saloni Permalink
March 06, 2014, 16:41

Paul Aguilar Permalink
May 04, 2016, 18:45

Start here.

March 02, 2017, 19:29

I will be uploading solutions to CLRS book soon at

Leave a new comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "browser_84": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.