How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final.

I'm trying to find out how to prove the algorithm has worst case running time of $n^3$.

Thanks

-

Maybe I am missing something, but if you look at the pseudocode on the wikipedia article, then these are the only bits that iterate over $n$

for each i = 1 to n
....
for each i = 2 to n -- Length of span
for each j = 1 to n-i+1 -- Start of span
for each k = 1 to i-1 -- Partition of span
....


The first set of nested loops iterates to $n$ once $O(n)$ The second bit has lots of twiddly bits, but there are 3 loops to $n$ (or something that scales with it), so the second is order $O(n^3)$, and the whole thing is $O(n^3)$. You could do it more formally by saying that it

for each i = 2 to n -- Length of span
for each j = 1 to n-i+1 -- Start of span
for each k = 1 to i-1 -- Partition of span
SOMETHING THAT TAKES TIME 1


then writting the running time as a sum $$t = \sum_{i=2}^n \sum_{j=1}^{n-i+1} \sum_{k=1}^{i-1} 1$$ which you can obtain an expression for $$t = (n^3 - n)/6$$ so $$O(t) = O(n^3)$$

-