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?

Postby Rigaudon » Tue Apr 05, 2011 9:43 pm UTC

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?

Postby achan1058 » Wed Apr 06, 2011 2:38 am UTC

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.

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

Re: How do you interpret notation in pathfinding?

Postby silverhammermba » Wed Apr 06, 2011 3:32 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests