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!

## How do you interpret notation in pathfinding?

**Moderators:** gmalivuk, Moderators General, Prelates

### 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.

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.

### Who is online

Users browsing this forum: No registered users and 5 guests