Hi all,

I urgently need help with below, have two questions (one based on the original algorithm and a second set of questions based on what I want to do) and would greatly appreciate if someone could help me with them:

Original algorithm:

I have an implementation of a greedy routing algorithm (computer networking) and need to discuss the complexity. With the original greedy routing algorithm, devices (nodes) offload data (packets) to one of their neighbour nodes by choosing the neighbour node that makes the greatest forward progress towards the destination i.e. achieves the greatest distance.

Based on what I’ve read the complexity is described as follows:

For a nodeuwith a set of neighboursN(u),the complexity of calculating the distance fromuto anyu’s neighbours isO(|N(u)|). If is theΔaverage node degree, the computational complexity of the algorithm for each node can be generalised as O(Δ^{2}).Question 1: I think this should be O(Δ) not O( Δ^{2}). Am I correct?

Modified algorithm:

So I’ve modified the algorithm so that not only will a nodeuwill still check the distance to all of its neighbours butifone of those neighbours is a non-moving node (lets call itr),uchecks the distance betweenrand all ofr’s non moving neighboursN_{r}(r).Question 2: How do I represent this with O notation? O(Δ +x) wherexis the average non moving neighbour degree? (Side note I don’t think this is correct given that nodeuwould usually only have one/two non moving neighbours or indeed often none at all).

Many thanks in advance.