Videos / DSA

Episode 7 of 22 · DSA, end to end

Time and space complexity: counting without counting

Chapters

1. Two machines, one program0:00
2. Everything the clock also timed0:15
3. Count the basic operation0:31
4. The count is a function0:48
5. Growth beats the clock1:05
6. The six shapes you meet1:22
7. A speed limit, not a speed1:40
8. The definition, properly1:55
9. Why the constants go2:12
10. Omega, and then theta2:29
11. The bound people abuse2:47
12. Cases are a second axis3:03
13. Sequential blocks add3:21
14. Nested loops multiply3:36
15. Half of quadratic is quadratic3:54
16. The loop that halves4:10
17. Two inputs, two letters4:28
18. The cost hiding in the call4:43
19. The bill that arrives once4:59
20. Push, and the day it copies5:17
21. Double, never add5:33
22. Add every copy up5:49
23. So the average push is constant6:06
24. Amortised is not average case6:23
25. The second meter6:42
26. Auxiliary, not total6:59
27. In place means constant7:18
28. The stack is space too7:35
29. Depth, not calls7:52
30. Buy time with space8:11
31. The map is not the road8:32
32. The constants are still there8:49
33. The model says memory is flat9:08
34. Same O, different day9:25
35. The input you actually get9:41
36. What it is actually for10:01
37. The whole thing10:19

Time and space complexity: counting without counting. Here is a stopwatch and two laptops. The same sorting program takes four seconds on one and one second on the other. So which number goes in the textbook? Neither. Seconds measure

Mark as watchedSaved in this browser only.