*David A. Tanzer, February 11, 2011*

In Part 6, we saw a program with quadratic complexity. The collection of all languages that can be decided in $O(n^k)$ time for some $k$ is called P, for polynomial time complexity.

Now let’s consider languages that appear to require time that is exponential in the size of the input, and hence lie outside of P.

Here is a decision problem that is believed … Read more

*David A. Tanzer, February 10, 2021*

**Quadratic complexity**

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity.

```
def square_length(text):
# compute the square of the length of text
# FIXME: not the most elegant or efficient approach
n = length(text)
counter = 0
for i = 1 to n:
for j = 1 to n:
counter
```

…

Read more
*David A. Tanzer, February 9, 2021*

**Big O analysis**

Recall our function $f(n)$ from Part 4, which gives the values 2, 13, 14, 25, 26, 37, …

Using ‘big O’ notation, we write $f(n) = O(n)$ to say that $f$ is linearly bounded.

This means that $f(n)$ will eventually become less than some linear function.

As we said, $f(n)$ has a “rough slope” of 6. So f could never … Read more

*David A. Tanzer, February 8, 2021*

**Summarizing computational complexity**

In Part 3 we defined, for each program P, a detailed function P'(n) that gives the worst case number of steps that P must perform when given some input of size n. Now we want to summarize P into general classes, such as linear, quadratic, etc.

**What’s in a step?**

But we should clarify something before proceeding: what is meant by … Read more

*David A. Tanzer, February 7, 2021*

**A detailed measure of computational complexity**

In Part 2, we identified language complexity by how “difficult” it is for a program to decide if some given text is a sentence of the language — in other words, by the complexity of the decision problem for the language.

Note there may be many decision procedures — which are implementations of functions – that solve … Read more

*David A. Tanzer, January 30, 2021*

**Decision problems, decision procedures and complexity**

In Part 1, we introduced the formal idea of a language, as being just a set of sentences. Now let’s approach the topic of language complexity.

For any given language, there is an associated *decision problem*: given a candidate string of characters, determine whether or not it belongs to the language. A *decision procedure*, or … Read more

*David A. Tanzer, December 31, 2020*. *This article was cross-posted to Azimuth, click here to discuss it.*

**A simple view of languages**

How complex is the English language? The question has many dimensions and nuances. What does complexity mean, and how could it be measured? This a tough nut to crack, so in this post we’ll make a retrenchment and reconsider the question in a more formal setting — … Read more

*David A. Tanzer, December 29, 2020*

## A leaf as a tree of pipes

Last time we set out the model of a leaf as a set of square cells in the plane. But there’s more structure to be defined: the veins.

All the veins taken together make up a ‘transport system’ for pumping fluid from the root to each of the cells.

Biological note: The cells need water to do … Read more

*David A. Tanzer, December 25, 2020*

## Leaf shape: an optimization in nature

On this Christmas day, let us take a moment to think of the tree, and wonder how it actually grows. Slowly move your attention to the leaves, and ponder how they grow. Next, forget about this type of leaf, for a conifer, with parallel veins — as our true subject is the growth of leaves with branching veins. … Read more

*David A. Tanzer, August 24, 2020*

# Continuous and discrete flows in epidemic models

The standard compartmental models for SIR, SEIR etc. use the rate equations for the dynamics, and hence assume a continuous flow model.

This works well, particularly due to the fact that population sizes in epidemics are “large”, on the order of millions of individuals, and the law of large numbers kicks in, which tells us that we … Read more