Complexity studies of algorithms usually involve
time and space analysis of the solution. In principle, the same types of calculations can be applied to potential
Origin of Life (OOL) theories. Unlike computational algorithms, these
ALgorithms (sorry, poor pun) are unknown (and, probably, unknowable).
However, there are absolute limits to the time and space available. The earth has only been a cool surface for around 4 billion years; also, obviously, there is only a limited surface area on the planet. A seemingly important question of the number of earth-like planets in the Universe I will ignore. Many planets have been discovered in the last few years, but the 'ours is the lucky planet' explanations are somewhat flat.
So, what sort of computer is Life? No, it's not running Linux, you zealots! Rather, it's a parallel, concurrent, molecular computer - organised in a heirarchy of scales from nanometers to meters. Fanciful analogies are easy to construct, and so I will. Consider enzymes to be processors; substrates are 'packets' of information. The metabolic network is constantly rewired as the enzyme-processors and the substrate-packets move around the cytoplasm.
Conceptually, this might seem difficult - after all, 'hardware' (enzymes] and 'software' (small molecules) are practically the same. However, this is not that much of a problem; after all, optical switching might allow networks and computers to use light, seamlessly. Enzymes are polymers of amino acids; yet cells construct amino acids using enzymes. DNA codes for enzymes that make DNA. This very circularity is not only useful, but inevitable.
Start, then, with a 'soup' of components (nucleotides, amino acids, sugars) and an energy source. This could be the Sun, or an underwater volcano - it doesn't matter. The point is that structures will tend to form to exploit this energy, given sufficient mixing.