Definition EFFECTIVELY-O(1)

An algorithm ECA on a random access machine is effectively constant-time if ECA is not charged for entirely parsing its inputs and printing its output and ECA's processing time after parsing and before printing is constant-time.

Definition suggested by Griffin Schneider and Christopher Souvey. http://piazza.com/class#winter2012/cs4800/84

Feedback from Professor Viola: definition sounds new to me. Related concepts: streaming algorithms, property checking, spot-checking.

Discussion

Once ECA has its inputs in the random-access memory (RAM), it produces the updated RAM in constant-time. In our application, ECA reads a constant number of linear arrays plus an additional array that serves as template for the output array. ECA then inspects a constant number of input array elements and updates a constant number of elements in the output array.

We call the algorithm effectively O(1) because only the input/output steps are linear time but the processing itself is constant on a random-access machine. A random access machine has unit cost for read and write access to all of its memory cells. In a programming language that supports call-by-reference, the constant time behavior can be effectively benefitted from.

Examples

Function Problem: Not a Tautology

Consider a DNF (a Boolean formula in disjunctive normal form) with n variables and only two conjunctive clauses m1 and m2. Do m1 and m2 cover all 2^n assignments? If they don't, give an uncovered assignment which makes the DNF false.

The input consists of m1 and m2 plus the assignment which (e.g.) sets all n variables to true. This assignment is modified by the algorithm to produce the output assignment.

Function Problem: LeafCovering

A generalization of the above. A problem appearing in type-checking multiple dispatch languages.

Given n trees T1, ... ,Tn and two nodes m1 and m2 of the graph cartesian product GCP(T1, ... ,Tn), if m1 and m2 don't cover all leaves, find an uncovered leaf.