Re: Help with Big O Notation

Hey kerrymaid.

Can you please outline how one checks the distance in terms of code or pseudo-code?

Re: Help with Big O Notation

Hi Chiro,

u = node that is attempting to forward the data packet

v = node u’s neighbour i.e. in transmission range of node u

d = destination of the data packet

N(u) = Node u’s neighbour table

dist = function to calculate the straight line shortest Euclidean distance

for every v in N(u):

distance = dist (d,v)

choose v that makes max distance to d (assuming its better than dist(u,d))

So basically the for loop will execute as many times as you have neighbours i.e. N(u) times.

So if the size of N(u) is the number of neighbours in a node u’s neighbour table i.e. the node degree, and if the average node degree is represented as Δ, then the complexity of the system is O(Δ)…in my mind anyway….

What do you think? And if this is correct I’m trying to figure out how this impacts question 2.

Thanks,

kerrymaid.

Re: Help with Big O Notation

Will this be recursive though? Does every neighbour call its own version using its own neighbours?

Re: Help with Big O Notation

yes, every neighbour will call their own version

e.g. Assume node A is sending to node E and it is routed through B, C and D to get to D.

Node A might have 8 neighbours and so it will execute 8 times. Node B might have 6 neighbours and it will execute 6 times, node C might have 10 neighbours etc etc.

In terms of the Big O notation does this impact how the complexity is denoted?

Re: Help with Big O Notation

It will depend on the number of nodes and the topology of the graph. If you can roughly use a graph that is say square then the largest distance will be along the diagonal. If you use a circle then the largest distance is always the radii. However sparse the graph is with respect to its geometry will also factor in too.

Basically this will be an exponential type algorithm (up until the maximum number of nodes needed to call) unless you use pre-computed information.

For example if nodes keep querying the network for new nodes and save any extra information in a local table, then this could be used to look-up a node by using the relationship between your table and anyone elses table.

The above would be very good in terms of computational complexity and it only requires that you have more memory.