# Expressing Computational Complexity in Job EstimatesΒΆ

The complexity module parses and processes jobestimate or gb_memory parameters that use Big-O notation to make statements about the complexity of the task they are to run. This is not a highly engineered or terribly elegant piece of code, so there are lots of ways to produce ill-diagnosed syntax violations. See Hacks – Egregious.

Syntax:

```
jobestimate = O(estimate)
```

estimate can include the following small vocabulary of terms:

```
Q, unit, function, and operator::
estimate := Q*unit or function(Q*unit) or function(Q+Q*unit)
[The behavior of this one, function(Q+Q*unit), is questionable, sorry]
```

- Q -> either a TIME, for a jobestimate, or a SPACE, for gb_memory
- unit can be one of samples,chr21,lines,size
- function can be one of log(),sqrt(),square(),cube()
- operator, either + (addition) or * (multiplication)
- TIME is of the form H20M30 or 20:30:00 (in the second form, seconds are required)
- SPACE is a number plus one of the forms MB, GB, or (heaven forfend) TB, e.g., 20GB or 200MB.

The estimate should include Q times a unit at least.

units:

```
samples -> (number of samples)
chr21 -> length of each human chromosome divided by the length of chromosome 21
lines -> (number of lines in file)/100
size -> (size of file)/10000
```

functions:

```
log() -> log base 10 of argument (one of samples,chr21,lines,size)
sqrt() -> square root of argument (one of samples,chr21,lines,size)
square() -> square of argument (one of samples,chr21,lines,size)
cube() -> argument cubed (one of samples,chr21,lines,size)
```

Examples:

```
jobestimate = O(H01*samples)
jobestimate = O(M30*square(samples))
gb_memory = O(1GB+1GB*chr21)
```