## How do you interpret notation in pathfinding?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Rigaudon
Posts: 1
Joined: Tue Apr 05, 2011 9:40 pm UTC

### How do you interpret notation in pathfinding?

Hi everyone.

I've been doing a bit of research about path-finding algorithms recently, but I can't find anything on the expression that looks like O().

For example, the worst-case performance for breadth-first search is O( | V | + | E | ) = O(b^d), according to Wikipedia.

Can anyone explain to me what this means please? Thanks!

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

### Re: How do you interpret notation in pathfinding?

Big O notation

Since the runtime of algorithms tend to depend on the input size, the performance descriptions are written as such. Furthermore, the proportional constants doesn't matter much, since they are machine dependent. Simply, the notation says, if f is O(g), then f(t) <= C*g(t) for some constant C and for large enough t>=T.

silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

### Re: How do you interpret notation in pathfinding?

The simplest way to understand big O is that it describes how quickly a function increases. In your specific case, it refers to how long it takes to find paths in terms of the size of the graph.