algorithm performance measure

[Micko]

Hello, reading one article I found that performance one algorithm is measured in O(log* V). Can you explain me what log* V means. I generally understand big Oh notation and I know what O(NlogN) means, but what is the meninig of '*'?

[Narue]

What algorithm? Which article, and can you post the relevant parts? I know that log V is relatively common with graph algorithms where V is the vertex count, but I've never seen an asterisk in there. It could just be a typo.

[Micko]

What algorithm? Which article, and can you post the relevant parts? I know that log V is relatively common with graph algorithms where V is the vertex count, but I've never seen an asterisk in there. It could just be a typo.

"Tarjan showed in 1975 that weighted quick union with path compression requires following less than O(lg* V ) pointers in the worst case, and that any pointer-based algorithm must follow more than a constant number of pointers in the worst case for some input. In other words, there is no point looking for some new improvement that will guarantee to solve the problem with a linear number of i = a[i] operations. In practical terms, this difference is hardly significant, because lg* V is so small; still, finding a simple linear algorithm for this problem was a research goal for many years, and Tarjan's lower bound has allowed researchers to move on to other problems. Moreover, the story shows that there is no avoiding functions like the rather complicated log* function, because such functions are intrinsic to this problem."

I don't think it's a typo because it repeats...

[Narue]

I don't know. It's either a placeholder for the base of the logarithm, or some funky notation that I'm not familiar with. Send an email to the author of the article. :) I've found that to be surprisingly effective (except with Bob Sedgewick because he doesn't respond in a reasonable amount of time, and Don Knuth because he doesn't do email...though he's very pleasant through snailmail). ;)

[Micko]

I don't know. It's either a placeholder for the base of the logarithm, or some funky notation that I'm not familiar with. Send an email to the author of the article. :) I've found that to be surprisingly effective (except with Bob Sedgewick because he doesn't respond in a reasonable amount of time, and Don Knuth because he doesn't do email...though he's very pleasant through snailmail). ;)

I didn't know Knuth is still alive :).
P.S. Nice avatar

[Narue]

>I didn't know Knuth is still alive
He'd better not die on me! I'm waiting with baited breath for the next chapters of TAoCP.