There is an error in the slides: The complexity of Eisner's algorithm in O(n^3). The slides incorrectly state that the chart is of size O(n); the chart is actually of size O(n^2). Because there is a linear search over subspans, the total complexity is O(n^3) (as stated in the slides).
Updated version here:
https://www.youtube.com/watch?v=ZT1Et5wd1SQ
