[rollie42]

I occasionally want to look up details of an algorithm, but stumble on some of the identifiers used in many articles. For example, wikipedia's a* description lists the worst case performance of the algorithm as:

O(|E|) = O(b^d)

big-O notation I'm familiar with, but the rest I'm not. I assume the first part is 'the absolute value of E'; I can't imagine there being a negative number of edges, so I'm not sure exactly how to interpret that. The other part is even more confusing; I don't see 'b' or 'd' defined in the beginning of the article (though 'd' is later to defined to be 'the length of an edge').

So while I am curious what these values mean, the more important question I have is: how can I figure this out without asking? I suspect googling 'b' and 'd' would not help me too much!

[sepp2k]

E isn't the number of edges here, it's the set of edges. And for a set |.| means "length". So |E| is the length of the set of edges, or in other words: |E| is the number of edges. d is probably the maximum degree of the nodes (i.e. the maximum number of edges per node). I don't know what b is.

Generally that kind of thing should be defined in the article. When it isn't (like in this case), your best bet might be to find a better article.

[rollie42]

Thanks sep, the info about what |E| might mean is very useful! As for "b^d", I'm guessing based on other reading that:
b = the max number of edges from a node and
d = the depth of the search (i.e., the length of the shortest path)