>One common subtopic I would recommend having a basic familiarity with is amortized big-O, aka expected big-O, whereby you use some neat probability theory to s

>One common subtopic I would recommend having a basic familiarity with is amortized big-O, aka expected big-O, whereby you use some neat probability theory to say that the expected value of an operation is, for instance, O(1) even though sometimes it may be O(n) for individual calls. Isn't he mixing two terms here? If I recall correctly amortisation shows up in deterministic algorithms where some steps might frontload work that consecutively makes others easier. For instance you have some graph algorithm that looks at all the neighbours of some node in every iteration which means the runtime theoretically depends of the degree of the node, but if you can guarantee that each edge will only be inspected once your total time complexity only depends on the number of edges. On the other hand expected time complexity is used when you run a probabilistic algorithm like quicksort, where individual sort calls actually have a variance in time complexity.