this will not be funny to many

[trochee]

Labmate just summarized a paper: "the naive algorithm is O(2ⁿ). He spends 10 pages explaining how his algorithm is O(1.9601ⁿ)."

My answer: "So if n is large, it's intractable anyway, and if n is small, it doesn't matter anyway."

"Basically, yeah."

I'm glad it's not me trying to justify that paper to the reading group.

Comments

[marnanel.livejournal.com]

wtf? the whole point of big O notation is that O(2ⁿ) is equivalent to O(1.9601ⁿ).

[marnanel.livejournal.com]

(which was probably your friend's point, I suppose.)

[trochee.livejournal.com]

well, they define a function big-O-star which discards polynomial-and-less, so under their definition O*(2ⁿ) ≠ O*(1.9601ⁿ).

But it's not a very interesting thing to prove.

[tulip-tree.livejournal.com]

But it's not a very interesting thing to prove.

No, it's really not. But I'm one of the few who did find this post funny. :)

[trochee.livejournal.com]

I live to serve.

A little linguistics, a little computer science today: everybody's happy.

[http://users.livejournal.com/merle_/]

*laugh* Thanks.

There is some improvement there. 1.9601^10 ~= 837, a bit better than 1024. For huge problems where n>30, it's nice to have a slightly faster algorithm. But... yeah, it seems pretty insignificant.