MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

Lecture 2: Asymptotic Notation, Recurrences, Substitution, Master Method

author:Erik Demaine, Center for Future Civic Media
published: Feb. 10, 2009, recorded: September 2005, views: 3547

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Introduction to Algorithms - Lecture 2
1:07	Asymptotic notation (1)
2:47	Asymptotic notation (2)
3:47	Asymptotic notation (3)
3:48	Asymptotic notation (4)
3:55	Set definition of O-notation (1)
4:40	Set definition of O-notation (2)
4:55	Set definition of O-notation (3)
5:14	Macro substitution (1)
6:26	Macro substitution (2)
7:59	Macro substitution (3)
10:24	Ω-notation (lower bounds) (1)
10:32	Ω-notation (lower bounds) (2)
11:16	Ω-notation (lower bounds) (3)
12:22	Θ-notation (tight bounds) (1)
13:22	Θ-notation (tight bounds) (2)
13:32	ο-notation and ω-notation (1)
14:30	ο-notation and ω-notation (2)
16:51	Solving recurrences
17:15	Substitution method (1)
18:52	Substitution method (2)
23:19	Example of substitution (1)
27:12	Example of substitution (2)
28:18	Example of substitution (3)
28:41	A tighter upper bound (1)
28:54	A tighter upper bound (2)
29:55	A tighter upper bound (3)
30:13	A tighter upper bound (4)
30:54	A tighter upper bound (5)
31:53	A tighter upper bound (6)
34:05	A tighter upper bound (7)
37:39	Recursion-tree method
38:52	Example of recursion tree (1)
40:07	Example of recursion tree (2)
40:09	Example of recursion tree (3)
40:39	Example of recursion tree (4)
41:05	Example of recursion tree (5)
41:19	Example of recursion tree (6)
43:54	Example of recursion tree (7)
44:21	Example of recursion tree (8)
45:37	Example of recursion tree (9)
48:51	The master method
51:45	Three common cases (1)
53:30	Three common cases (2)
54:56	Three common cases (3)
57:25	Examples (1)
58:47	Examples (2)
59:44	Examples (3)
60:01	Examples (4)
61:49	Idea of master theorem (1)
63:22	Idea of master theorem (2)
65:54	Idea of master theorem (3)
66:15	Idea of master theorem (4)
66:56	Idea of master theorem (5)
68:15	Idea of master theorem (6)

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

"My name is Erik Demaine. You should call me Erik. Welcome back to 6.046. This is Lecture 2. And today we are going to essentially fill in some of the more mathematical underpinnings of Lecture 1. So, Lecture 1, we just sort of barely got our feet wet with some analysis of algorithms, insertion sort and mergesort. And we needed a couple of tools. We had this big idea of asymptotics and forgetting about constants, just looking at the lead term. And so, today, we're going to develop asymptotic notation so that we know that mathematically. And we also ended up with a recurrence with mergesort, the running time of mergesort, so we need to see how to solve recurrences. And we will do those two things today. Question? Yes, I will speak louder. Thanks. Good..."