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
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) $