10. Understanding Program Efficiency, Part 1

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
Instructor: Prof. Eric Grimson

In this lecture, Prof. Grimson introduces algorithmic complexity, a rough measure of the efficiency of a program. He then discusses Big "Oh" notation and different complexity classes.

License: Creative Commons BY-NC-SA

[Danny]

Wow I'm watching a class from the MIT in the comfort of my room... What a time to be alive :')

[spacewad]

This is what I love about foreign universities. So much passion into teaching. Thanks OCW for allowing someone like me in a third world country to experience such excellent teaching.

[MrSrijanb]

OCW for me, is one of the best initiatives in the world. thanks MIT!

[leixun]

*My takeaways:*
1. Timing a program and its problems 10:30
2. Counting operations and its problems 12:35
3. The amount of time that the code takes depends on its input 20:50
4. Big O notation 26:05
5. Focus on the term that grows most rapidly 30:05
6. Types of orders of growth 32:35
7. Analyzing programs and their complexity 33:30
8. Complexity classes 36:28
9. Complexity growth 37:25

[gfang]

Prof. Eric Grimson I miss you! You introduce me to the whole field of computer science!

[zlmsailor]

There must be years of accumulated experience and knowledge to make a lecture smooth and easy like this. Salute to Dr. Grimson.

[muhammadmubashirullahdurra]

old is Gold.
Im glad we have seniors!

[鄭心和]

​​0:02:49 Want to understand efficiency of programs
0:03:25​ Want to understand efficiency of programs
0:03:57 Want to understand efficiency of programs 0:06:00 0:08:00
​0:10:07 How to evaluate efficiency of programs ​0:11:52
​0:14:00​ Counting operations 0:16:00 0:17:42
0:21:16 Different inputs change how the program runs
0:23:17 Best case Average case Worst case ​0:26:57 0:28:00​
0:30:13 Simplification examples ​
0:32:40 Type of orders of growth
0:35:53 ​Analyzing program and their complexity
0:36:54 Complexity Classes ​0:38:00​
0:39:36 Linear search on unsorted list
0:42:35 ​Constant time list access
0:44:02 Linear search on sorted list
​0:45:30 ​Linear Complexity
0:46:46 Quadratic complexity 0:50:00

[andrearivera]

I have been trying to understand how to identify the number of operations in an algorithm and the order growth for 4 weeks since my course started. Your explanation is so detailed that it is all clear. Thank you so much, Professor!
I will keep following your videos.

[ketkiambekar]

The best resource out there for understanding Big O notation. Period.

[moyakubu]

I love this lecture, got some of the things I was confused about clarified. Thank you!

[SGspecial]

The man gives great effort. Admirable!

[massumpcao]

Thank you, professor, for these great lectures. I just had an job test and did great thanks to you

[diabellilife]

He's by far the most amazing professor I've ever seen on the entire internet. This is how the educational level of a country raises as a rocket, by having this kind of people in their classrooms.

[PankajKumar-jiig]

Thank You Professor, Hope you are well.

[shikharupadhyay]

Experienced teachers are at a different level!!!!

[xer_t]

when you are watching this on 2022 and the lecturer says "WE USE OMICRON! GOD KNOWS WHY! SOUNDS LIKE SOMETHING FROM FUTURAMA!"
I really feel that😐

[GThomas]

a not so simple topic explained in a simple way. that is the mark of a good teacher.

[jongpark]

35:18 is hilarious!
I wish I went to MIT just for this professor!!!

[leonzheng]

top professors, top students, top university, thanks MIT OCW!