Results 1 to 6 of 6

Math Help - Help with Big O Notation

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    42

    Exclamation Help with Big O Notation

    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 node u with a set of neighbours N(u), the complexity of calculating the distance from u to any uís neighbours is O(|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 node u will still check the distance to all of its neighbours but if one of those neighbours is a non-moving node (lets call it r), u checks the distance between r and all of rís non moving neighbours Nr(r). Question 2: How do I represent this with O notation? O(Δ + x) where x is the average non moving neighbour degree? (Side note I donít think this is correct given that node u would usually only have one/two non moving neighbours or indeed often none at all).

    Many thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,846
    Thanks
    677

    Re: Help with Big O Notation

    Hey kerrymaid.

    Can you please outline how one checks the distance in terms of code or pseudo-code?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    42

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,846
    Thanks
    677

    Re: Help with Big O Notation

    Will this be recursive though? Does every neighbour call its own version using its own neighbours?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2009
    Posts
    42

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,846
    Thanks
    677

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Big O-Notation Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2012, 06:59 AM
  2. I need help with some notation.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 12th 2012, 02:01 PM
  3. Notation help
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2011, 09:58 AM
  4. Replies: 1
    Last Post: March 10th 2011, 02:23 AM
  5. Replies: 1
    Last Post: August 26th 2009, 12:40 PM

Search Tags


/mathhelpforum @mathhelpforum