In the statement "The weighted quick-union algorithm follows at most lg N pointers to determine whether two of N objects are connected" what does lg stand for?
views:
83answers:
2
+9
A:
lg N stands for the logarithm of N. It is common in computing to use lg (in contrast to log) to explicitly mean the base-2 logarithm, but that's not universal.
jk
2010-01-12 14:19:47
if its big-O notation then the logartihm base is a constant which is irrelavent anyway
jk
2010-01-12 14:25:19
But there's no big-O visible in the statement, and it is not too unlikely that `lg N` could actually be the upper bound without any constant factors.
jk
2010-01-12 14:28:16
+1
A:
Are you sure your source says "1g N"? Because that looks more like "lg N" == "log N" to me... You might want to read up on the Disjoint-Set data structure, especially the part with path compression (always having a direct pointer to the head) and ranking (saving the weight/size/rank of a set) . (http://en.wikipedia.org/wiki/Disjoint-set_data_structure)
Hope this helps.
jmiserez
2010-01-12 14:24:41