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.