12. Understanding Time Complexity in Computation ⏱️

Explore the fundamentals of time complexity in computation with MIT's 18.404J course by Michael Sipser. Full course available online.

12. Understanding Time Complexity in Computation ⏱️
MIT OpenCourseWare
40.9K views β€’ Oct 6, 2021
12. Understanding Time Complexity in Computation ⏱️

About this video

MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser
View the complete course: https://ocw.mit.edu/18-404JF20
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY

Quickly reviewed last lecture. Gave an introduction to complexity theory. Discussed limited complexity model-dependence for reasonable models. Defined TIME(t(n)) complexity classes and the class P. Showed that PATH is in P.

License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu
Support OCW at http://ow.ly/a1If50zVRlQ

We encourage constructive comments and discussion on OCW’s YouTube and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at https://ocw.mit.edu/comments.

Tags and Topics

Browse our collection to discover more content in these categories.

Video Information

Views

40.9K

Likes

468

Duration

01:25:37

Published

Oct 6, 2021

User Reviews

4.4
(8)
Rate:

Related Trending Topics

LIVE TRENDS

Related trending topics. Click any trend to explore more videos.