## An Example of Exponential Runtime

This is a question any theory-oriented friends of mine should feel free to jump in on.

So I wanted to make some graphs for explaining Big O. And I wanted to include exponential functions on that graph. But unlike my previous examples of such things, I didn’t want to say “oh wow, look at this graph of 2^n….see how terrible it is” because I know that real exponential functions in practice are often much happier than 2^n. I wanted real run-time data, ideally using source code from some trustworthy seeming source (i.e. not me).

“So heck,” said I, “surely Mathematica has implementations of some of these famous NP-Complete problems. I’ll run some of those and I think that that’s at least plausibly trustworthy.” So I poked around and found some graph algorithms – specifically traveling salesman and Hamiltonian cycle.

Then came the difficulty of generating good problem examples. I initially thought I’d just use random graphs but the runtime varied so much it just wasn’t reasonable. Then I noticed that if I passed in complete graph to Hamiltonian Cycle with one completely disconnected vertex, the Hamiltonian Cycle algorithm would be pretty dang slow:

But was it really exponential? This is where I’m stuck. I don’t really understand the algorithm that’s generating these solutions – for all I know it might be detecting the disconnected vertex (albeit somewhat late) and might be evidencing merely some (bad) polynomial time.

HamiltonianCycle[g_Graph,flag_:One] := Module[{s={1},all={},done,adj=Edges[g], e=ToAdjacencyLists[g],x,v,ind,n=V[g]}, ind=Table[1,{n}]; While[ Length[s] > 0, v = Last[s]; done = False; While[ ind[[v]] < = Length[e[[v]]] && !done, x = e[[v,ind[[v]]++]]; done = !MemberQ[s, x] && (Length[s] == 1 || BiconnectedQ[DeleteVertices[AddEdges[g, {{1, x}}], Rest[s]]]) ]; If[done, AppendTo[s,x], s=Drop[s,-1]; ind[[v]] = 1]; If[(Length[s] == n), If [MemberQ[adj, Sort[{x, 1}]], AppendTo[all,Append[s,First[s]]]; If [SameQ[flag,All], s=Drop[s,-1], all = Flatten[all]; s={} ], s = Drop[s,-1] ] ] ]; all ]

Does that look familiar to anyone? Any guesses to Big-O for this kind of input?

OR – say you wanted to provide an example of real running exponential function. What would you use instead of my Hamiltonian Cycle hack?

Ok, I found the textbook that this function was based on. And indeed, it is not exponential – actually it only checks every pairing of vertexes. Ok…let me see if I can trick it further.