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 '*'?
Micko 2 Junior Poster
Narue 5,707 Bad Cop Team Colleague
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 2 Junior Poster
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 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 5,707 Bad Cop Team Colleague
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 2 Junior Poster
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 5,707 Bad Cop Team Colleague
>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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.