We can simulate the PDA and parse the language with the following operations (vaguely):
- Read the input symbol and top of stack - $O(1)$
- Check all the transition rules (must check all for non-determinism) - $O(|Transition rules|)$
- Update the stack and the set of states - $O(1)$
Due to non-determinism, the problem size increases and so does the complexity.
However, for deterministic context free languages, the complexity of this algorithm seems to be $O(n|Transition rules|)$ which is linear.
The complexity of CYK algorithm is $O(n^3|G|)$. From various sources it seems that the complexity of CYK algorithm is polynomial for deterministic languages. http://people.csail.mit.edu/madry/docs/linear.pdf
$|Transition rules|$ has a maximum value of around $|G|$ I think.
So, is this method really better than the CYK algorithm for deterministic CFLs or am I making a mistake in my analysis? If so, then where?
I'm assuming that $|G|$ = Number of production rules in grammar.