Algorithm Efficiency
A first introduction to algorithms and how to analyze their running time using O-Notation. The example used is Linear Search.
I like to talk slowly, so use playback speed of 1.25 for "normal" speed, or even faster.
This is the first video of a full course on Algorithms & Data Structures. You can find all videos in this playlist: • Data Structures & Algorithms
You can find the course with slides, quizzes and additional practice assignments here: https://canvas.instructure.com/course...
Timeline:
0:00 Algorithms
6:43 Correctness & Efficiency
12:42 Efficiency Analysis
15:22 Comparing growth orders
22:12 Linear Search
30:02 Better Linear Search
33:16 Efficiency
36:21 Elementary Operations
40:52 O-Notation: Theta
44:46 Analysis: Example 1
48:57 Analysis: Example 2
53:48 O-Notation: O and Omega
56:06 O-Notation: Quiz
1:00:54 Using Theta vs O
1:05:16 Recap
Typos/Mistakes:
at 18:00: the second logarithm property here should be log_c(a^b) = b*log_c(a) (a to the bth power) [thanks to panopticon]
at 45:29: less than or equal to 36 n^3 (not 36 n^2) [thanks to Lara Visser]