I need a layman's blurb on 'time' (as in for example, polynomial time)

I took a rather winding and incomplete road through maths (and comp-sci) in college, so some things I get, and some things I must have missed.

I need to wrap my head around what Math and Computer people mean by 'time' and/ running time.

I'm wondering what counts as a step: Does running a comparison count as a step? (If,then) All of the +-*/ count I believe. So if one says a = b + c + d, does that count as one step, where as {a = b + c, then a = a + d} is two steps?

Does it cost any extra steps to use a larger integer, rather than a smaller one, say?

Does x^3 require fewer steps than x*x*x?

Is there some underlying principle that guides whether something is a "step" or not?

• The whole point of $O(f(x))$ notation is that it lets us ignore nearly all of these sorts of details about what constitutes a "step", and this is exactly why it is used so universally. – MJD Oct 4 '13 at 17:36
• There's a lot of things we do to save memory in our heads, but that doesn't mean we never had to initialize it in the first place. I am vaguely familiar with big Oh. But taking care of details in the first case helps me worry less that I am missing something, so... – Mr. AM Oct 4 '13 at 17:43

What you're generally describing is better termed as "complexity". Complexity can be both in time (number of steps) and in memory or space, and is typically given in Bachman-Landau notation, the most common of them being "Big-Oh".

To your question, a "step" is more accurately described, in most algorithms, as "a block of code that executes in constant time". It doesn't matter how many actual operations there are in this block, what typically matters to computer scientists is that this block is input-independent (it will execute in the same time regardless of the input), and how many times you execute it while processing N input elements.

Some basic examples:

• Constant Time ($O(1)$) = "Return the first element in a list of N". No matter how large N is, the operation of producing the first element of a collection of N elements is virtually always as simple as making one calculation of a memory address and dereferencing whatever's there. Notice that's two operations (or more depending on how low-level you want to get), but we call this one "step", and this step executes once and only once for this particular problem.

• Log Time ($O(\log N)$) = "Return the left-most leaf from a balanced tree of N elements". A notable exception to the above tenet of constant-time access is when the collection is a binary tree structure. In a balanced binary tree, each non-leaf node has two children (or as many as the total number of elements allows). Finding the left-most leaf, which would be the lowest magnitude element, requires following the left branch from the root all the way to a leaf node. You will end up traversing one node per level of the tree, and each level has double the elements of the previous, therefore the number of levels represents the number of elements as a power of 2; a balanced, full tree of 5 levels will have 2^(5+1)-1 = 63 total elements. So, for this 63-element tree, finding the left-most leaf (or any single node for that matter) requires a number of iterations roughly equivalent to the base-2 logarithm of the total number of elements. There are a lot of possible logarithm bases; they are typically considered unimportant as the overall shape of the graph remains the same; as N increases linearly, the rate of increase in execution time actually slows.

• Linear Time ($O(N)$) = "Return the sum of all elements". Most aggregations, such as sums, minimums, maximums etc. require every element to be examined once and only once. Transformations, aka projections, are typically also linear-time. This complexity class encompasses the overwhelming majority of "everyday" list-processing tasks.

• NlogN Time ($O(N\log N)$) = "Sort all elements". Most of your "efficient" sorts, such as QuickSort and MergeSort, work by a "divide and conquer" strategy of splitting the collection in half in a recursive series. This creates log2(n) levels of recursion, and within each level all elements are touched once (to find their place in progressively larger or smaller lists). Other efficient sorts, like HeapSort, TreeSort etc work by building a data structure like a heap or binary tree in which certain ordering rules are followed during its construction. Inserting each of the N elements is a worst-case log(N) operation (traversing through all possible levels to insert as a leaf node), so building the construct is an NlogN operation, then traversing or deconstructing the structure to produce the sorted list is also an NlogN operation (as accessing each node is also a logN operation which is repeated N times).

• Quadratic Time ($O(N^2)$) = "Return all unique permutations of 2 elements from a list of N elements". To produce this result, you have to traverse the list once (to determine the first element), then for each element you encounter, you have to traverse the list completely a second time (to determine the second element, possibly skipping the position of the first element). This is a "loop within a loop" and requires N*N trips through the inner loop (in which you would form the pair and add it to the results).

• Cubic Time ($O(N^3)$) = "Return all unique combinations of three elements out of the list of N elements". In a combination, unlike a permutation, order is unimportant. So, while each element can be the first element of a combination, once it has been used as such, it should never be the second or third element because that will invariably produce a duplicate combination. So, the first loop will traverse all N elements. The second loop will travel X-1 elements for each trip through the first loop, where X is the current element of the first loop. The third loop will traverse Y-1 elements for each trip through the second loop, where Y is the current element of the second loop. So, the complexity is $N(N-1)(N-2)/2$ total traversals through the inner loop. While that is less than $N^3$, it grows at a similar rate to $N^3$ (the graphs are similarly-shaped), and therefore in Bachman-Landau notation we tend to reduce the expression to the fastest-growing term, which is $N^3$. We say that its complexity increases on the order of N-cubed.

Constant, Linear, Quadratic, Cubic and all other complexities that can be expressed as $O(N^k)$ for some $k >=0$ are "Polynomial time", and the class of computational problems of this complexity are PTIME. I believe logarithmic time and NlogN time are generally lumped in with the $N^k$ forms. Typically, this is the general threshold for "efficiency"; if it can be solved in polynomial time, then it is a practical algorithm for large-scale use.

• Exponential time ($O(k^N)$) = "Find a message that will produce a specific hash digest of N bytes given an ideal (uncrackable; no shortcuts) hash function" ($O(2^N)$ where generally $N>=128$). Or, "Solve the Tower of Hanoi for N discs" ($O(3^N)$), or "Produce all unique combinations of any number of N total elements" (the set of all subsets, aka the "power set"; by definition, $|P(N)| = 2^{|N|}$). The broadest class of problems are problems for which the "brute force solution" of simply trying every possibility is the most elegant known solution. The complexity of this class of problems is known as EXPTIME, and the number of inputs to such problems must be managed carefully, but there are a few useful EXPTIME algorithms in existence.

• "Power Tower" time ($O(^Nk)$) = This is the largest subclass of problems that are not "EXPTIME-complete" but are theoretically solvable. A "power tower" or exponentiation tower is an expression of the form $k^{k^{k^{k^{k^{...}}}}}$, where the number of exponents of the exponent is N levels tall. The relatively modest-looking tetration $^33 = 3^{3^3} = 7,625,597,484,987$, and it spirals totally out of control very quickly; $^43 = 3^{7,625,597,484,987}$ which is a quantity Windows calculator flatly refuses to evaluate.

• Thank you. May I ask, is this a math question or a computer question? I ask this because I wonder, do math people have a concept of 'time' in terms of steps, or is it only that computer people use process time as an arbitrary measuring stick? I imagine math people would want a concept of complexity just as much as computer people would. – Mr. AM Oct 5 '13 at 1:40
• It's more a comp sci question, but not because of any way of looking at it. Bachman-Landau's single biggest use is for computational complexity. – KeithS Oct 5 '13 at 1:43