What is the complexity of the next grammar

Question

I'm developing a Generalized Parsing Algorithm and I'm testing it with next rule

S ::= a | SS

Well, the algorithm is showing me all trees generated for the string composed of n a's.

For example next table shows the time used by the algorithm due to the quantity of a's

length  trees   time(ms)
1           1   1
2           1   1
3           2   2
4           5   2
5           14  2
6           42  2
7           132 5
8           429 13
9           1430    28
10          4862    75
11          16796   225
12          58786   471
13          208012  1877
14          742900  10206

I dont know what O (Big O notation) is my algorithm. How can i measure it because of course the time depends of three things:

1. The length of the string to parse
2. The grammar complexity
3. The performance of the algorithm

Answer 1

Big-O isn't a matter of measuring run-times; that's profiling. Big-O is a matter of algorithm analysis, which is impossible without seeing the algorithm.

Broadly speaking, break the algorithm down into basic operations, loops and recursive calls. The basic operations have a defined timing (generally, O(1)). The timing of loops is the number of iterations times the timing of the loop body. Recursion is trickier: you have to define the timing in terms of a recurrence relation, then solve for an explicit solution. Looking at the process call tree can offer hints as to what the explicit solution might be.

Answer 2

S can match any string of all a's.

Any binary tree with n leaf nodes could be a parse tree, and the number of such trees is given by the Catalan numbers.

Answer 3

We don't know the complexity neither because you didn't post the algorithm. But obviously there is a chance that you have an implementation that blows up pretty bad. The problem is not necessarily in the algorithm, thought, but in the grammar itself. A suitable preprocessor for the grammar could rewrite it to the more natural form

S ::= a | a S

which would be much more efficient to handle.