Instant Complexity

Analyzing the runtime complexity of algorithms is an important tool for creating efficient programs. Algorithms running in linear time are typically much faster than those requiring quadratic time for the same task. Therefore, preference should be given to linear-time algorithms.

Usually, the execution time of an algorithm is determined with respect to $n$ — the "size" of the input data. This can be, for example, the number of objects to sort, the number of points in a polygon, and so on. Since finding a formula describing the time complexity as a function of $n$ is often difficult, it would be great if this process could be automated. Unfortunately, this is not possible in general. However, in this task, you will analyze very simple programs where this can be done. Such programs are described by the following BNF grammar, where <\textbf{number}> can be any non-negative integer:

<\textbf{Program}> ::= "BEGIN" <\textbf{Statement list}> "END"

<\textbf{Statement list}> ::= <\textbf{Statement}> | <\textbf{Statement}> <\textbf{Statement list}>

<\textbf{Statement}> ::= <\textbf{LOOP statement}> | <\textbf{OP statement}>

<\textbf{LOOP statement}> ::= <\textbf{LOOP header}> <\textbf{Statement list}> "END"

<\textbf{LOOP header}> ::= "LOOP" <\textbf{number}> | "LOOP n"

<\textbf{OP statement}> ::= "OP" <\textbf{number}>

The runtime of such a program is computed as follows: an OP statement requires as many time units as the parameter specifies. A statement list inside a LOOP statement is executed as many times as its parameter indicates: by a given constant if a number, or $n$ times if $n$ is given. The runtime of a statement list is the sum of the runtimes of its components. Therefore, the total runtime depends on $n$.