View Question
 Question
 Subject: Complexity of DSA Category: Computers > Algorithms Asked by: jumpstart-ga List Price: \$99.00 Posted: 04 Apr 2005 19:28 PDT Expires: 11 Apr 2005 16:27 PDT Question ID: 505010
 ```Hello Researchers!! Reference: http://www.ieee-infocom.org/2001/paper/148.ps I know a few basic concepts of Algorithm analysis and Computational complexity stuffs. However, I don't know much about the details. I would like to know answers to my questions regarding that paper. ___________________________________________________________ 1. I would like to know the clear proof of the TheoremII.I ---in 3rd page to get the term O (mD/e) (I represent "e" for "epsilon") -------------------------------------------------------------------- 2. How the complexity of Dijkstra's algorithm is O (m+n log n)? to get the term O ((m+n log n)D/e) ---in 3rd page ____________________________________________________________ Help needed ASAP!! Thanks, Jumpstart```
 ```Dear jumpstart, 1. This proof is indeed a terse one, leaving out so much detail as to be incomprehensible on first sight. After reading it over many times, however, I came to understand what calculations are missing. The proof of Theorem II.1 begins by stating Lemma II.1, which is itself unproven. This lemma contains two separate statements that I shall prove independently. First, the lemma claims the following. Let P_tau(v) denote the cheapest path from the source to any vertex v in G_tau satisfying the delay constraint tau. The cost of P_tau(v) is no more than the cost of the cheapest path between s and v satisfying the delay constraint T in G. The claim says, in effect, that no path P_tau(v) can possibly cost more than the path P(v) computed by DAD(G,T) in the original graph. To see why this is so, consider that the path P(v) consists of k hops with costs c_1, c_2, ..., c_k. By definition, the sum of these costs is no greater than the delay threshold T. c_1 + c_2 + ... + c_k <= T If we take the same path through the tau-scaled graph G_tau, each of these costs is multiplied by tau/T and truncated to an integer. In other words, we take the floor of tau/T*c_i for each i from 1 to k. Hence, each cost in the tau-scaled graph is no greater than T/T*c_i. floor(tau/T*c_1) + floor(tau/T*c_2) + ... + floor(tau/T*c_k) <= tau/T*c_1 + tau/T*c_2 + ... + tau/T*c_k = tau/T * (c_1 + c_2 + ... + c_k) <= tau/T * T = tau The cost of the path P(v) in the tau-scaled graph G_tau is therefore no greater than tau. But if P_tau(v) is the cheapest path whose delay does not exceed tau, then the cost of P_tau(v) cannot be greater than that of P(v), which is itself a path whose delay does not exceed tau. The second claim in Lemma II.1 follows. Further, the delay of P_tau(v) in G is at most T(1 + D/tau) where D is the maximum length, in hops, of any cheapest path satisfying the delay constraint tau. Consider that the path P_tau(v) consists of j hops such that j <= D, and name the costs of the hops d_1, d_2, ..., d_j, so that the total cost of P_tau(v) in the tau-scaled graph G_tau is the following. d_1 + d_2 + ... + d_j <= tau Let us add j to each side of the inequality, then multiply each side by T/tau. (d_1+1) + (d_2+1) + ... + (d_j+1) <= tau + j T/tau*(d_1+1) + T/tau*(d_2+1) + ... + T/tau*(d_j+1) <= T + j*T/tau Now observe that each term T/tau*(d_i+1) is at least as great as the corresponding cost c_i in the original graph G. d_i = floor(tau/T*c_i) d_i+1 >= tau/T*c_i T/tau*(d_i+1) >= c_i Hence, the following obtains. c_1 + c_2 + ... + c_j <= T/tau*(d_1+1) + T/tau*(d_2+1) + ... + T/tau*(d_j+1) <= T + j*T/tau But c_1 + c_2 + ... + c_j is just the total cost of P_tau(v) in G. And since D is an upper limit on j, this total cost can be no greater than the following. T + D*T/tau = T(1 + D/tau) That concludes the proof of the lemma. The theorem then stipulates that tau >= D/e, with the following consequence for the cost of P_tau(v) in G. D/e <= tau T(1 + D/tau) <= T(1 + D/(D/e)) = T(1 + e) This guarantees that the algorithm DSA will terminate. Since the only variable amount of work done by DSA is in the call to subroutine DAD, the runtime of DSA is governed by that of DAD. And DAD, for its part, takes time proportional to mT, where T is the input delay threshold and m is the number of nodes in the input graph. On its first iteration, DSA calls DAD with delay threshold tau_0, for a cost of m*tau_0. On the second iteration, the delay threshold doubles to 2*tau_0, for a cost of 2*m*tau_0, and so on. We can simplify the resulting series as follows. m*tau_0 + m*2*tau_0 + ... + m*2^k*tau_0 = m*tau_0* (1 + 2 + ... + 2^k) = m*tau_0 * (2^(k+1) - 1) < m*tau_0 * 2^(k+1) = 4*m * tau_0*2^(k-1) < 4*m * D/e We drop the constant 4 to obtain an asymptotic runtime of O(m*D/e). 2. A succinct description of Dijkstra's Shortest Paths algorithm is given on the following web page. Dijkstra's algorithm keeps two sets of vertices: S the set of vertices whose shortest paths from the source have already been determined and V-S the remaining vertices. The other data structures needed are: d array of best estimates of shortest path to each vertex pi an array of predecessors for each vertex The basic mode of operation is: 1. Initialise d and pi. 2. Set S to empty. 3. While there are still vertices in V-S: 1. Sort the vertices in V-S according to the current best estimate of their distance from the source. 2. Add u, the closest vertex in V-S, to S. 3. Relax all the vertices still in V-S connected to u University of Western Australia: John Morris: Dijkstra's Algorithm http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html Observe that the main loop of the algorithm, labeled above with the outer number 3, runs once for each vertex in the graph. Thus, the main loop runs n times. We can neglect the outer Steps 1 and 2, which take constant time. The inner Step 1 requires that we find the closest remaining vertex to the vertices in S, which takes no more than log n operations if we store and update the vertex distances in a heap. Thus, the inner Step 1 contributes O(n log n) runtime to the total. The inner Step 2 takes a constant amount of time. The inner Step 3 is interesting because it requires, for each vertex chosen from the remaining vertices, that we consider each edge incident on it. How many times, then, do we look at each edge? Since each vertex is treated only once, and an edge connects two vertices, each edge of the graph is considered twice in the course of the algorithm. Thus, the cost of relaxing u's neighbors -- which are just the vertices neighboring it along the incident edges -- is 2m in total, or asymptotically O(m). Hence, the total cost of executing Dijkstra is O(n log n) + O(m) = O(m + (n log n)). It has been a pleasure to address this question on your behalf. If you find fault with any part of my answer, please inform me through a Clarification Request so that I may fully meet your needs before you assign a rating. Regards, leapinglizard``` Request for Answer Clarification by jumpstart-ga on 06 Apr 2005 23:28 PDT ```Dear LeapingLizard, First of all, I appreciate for your taking time to explain me the answer... However, I've asked for the refund as some of the *MAJOR* errors in your explanation made me have a *BAD* day :( I am sorry that there was no time for asking clarification and hearing back from you as I was needing it ASAP...as I mentioned in my Question. Just a word of thought, There is no need for clarification again. In case if you feel, that you can clarify and re-post some of the following issues before this question gets closed, that might really help someone in future, who might refer to it :) <<<>>> ---- """"The claim says, in effect, that no path P_tau(v) can possibly cost more than the path P(v) computed by DAD(G,T) in the original graph. To see why this is so, consider that the path P(v) consists of k hops with costs c_1, c_2, ..., c_k. By definition, the sum of these costs is no greater than the delay threshold T. c_1 + c_2 + ... + c_k <= T"""" ---- The paper never mentioned that sum of the <<>> is no greater than the delay threshold T. It should probably be delay...I guess ---- """"If we take the same path through the tau-scaled graph G_tau, each of these costs is multiplied by tau/T and truncated to an integer. In other words, we take the floor of tau/T*c_i for each i from 1 to k. Hence, each cost in the tau-scaled graph is no greater than T/T*c_i. floor(tau/T*c_1) + floor(tau/T*c_2) + ... + floor(tau/T*c_k) <= tau/T*c_1 + tau/T*c_2 + ... + tau/T*c_k = tau/T * (c_1 + c_2 + ... + c_k) <= tau/T * T = tau"""" ---- Again, costs never get multiplied by tau/T....or truncated and so on and so-forth... Also,....."""Hence, each cost in the tau-scaled graph is no greater than <<<>>"""" [should be tau/T*c_i] ---- """"The cost of the path P(v) in the tau-scaled graph G_tau is therefore no greater than tau. But if P_tau(v) is the cheapest path whose delay does not exceed tau, then the cost of P_tau(v) cannot be greater than that of P(v), which is itself a path whose delay does not exceed tau."""" ---- This is again wrong.....as it talks about cost..."The cost of the path <<>> [I guess, it should be P_tau(v) ] in the tau-scaled graph G_tau is therefore no greater than tau" """which is itself a path whose delay does not exceed tau.""" which is totally misleading!! ---- """"Consider that the path P_tau(v) consists of j hops such that j <= D, and name the costs of the hops d_1, d_2, ..., d_j, so that the total cost of P_tau(v) in the tau-scaled graph G_tau is the following."""" ---- Again, it should be delays, instead of costs. ---- """"Now observe that each term T/tau*(d_i+1) is at least as great as the corresponding cost c_i in the original graph G."""" ---- Same error! ---- """"The theorem then stipulates that tau >= D/e, with the following consequence for the cost of P_tau(v) in G."""" ---- Why suddenly D/e? where does that come from? Also, """consequence for the cost of P_tau(v) in"""....should be delay ---- = 4*m * tau_0*2^(k-1) < 4*m * D/e ---- What happened to the k value ? How the paper says k = ceil (log [d/e]/tau_0) ? How all of a sudden tau_0*2^(k-1) < D/e ?? And, the answer to the question number 2 is surely above average but not that much satisfactory! I understand that confusing between delay and costs everywhere in your answer is not that big a deal, if I already knew that's what going on. But, still you must realize this is DSA's complexity, which is basically DELAY SENSITIVE ALGORITHM and that makes its true explanation more important. I didn't really mean to get the full refund. I wanted to give at least half the price for your answer, and I came to know that every refunded answer gets 50% to the researcher however. Anyways, I am totally sorry!! Just thought that you should know...the reasons.. Once again, thanks for all your hard work and please don't mistake me! -JumpStart``` Clarification of Answer by leapinglizard-ga on 06 Apr 2005 23:41 PDT ```My algebra is correct. leapinglizard``` Request for Answer Clarification by jumpstart-ga on 06 Apr 2005 23:47 PDT ```How about this? ---- = 4*m * tau_0*2^(k-1) < 4*m * D/e ---- What happened to the k value ? How the paper says k = ceil (log [d/e]/tau_0) ? How all of a sudden tau_0*2^(k-1) < D/e ??``` Request for Answer Clarification by jumpstart-ga on 07 Apr 2005 00:07 PDT ```Ok, Probably this is not a good time to request for clarification (my previous post on 06 Apr 2005 23:47 PDT ) after talking about refund. Anyways, I do agree that your algebra is correct almost! Thanks, JumpStart``` Clarification of Answer by leapinglizard-ga on 07 Apr 2005 00:14 PDT ```Fine. Let us say no more about it. leapinglizard``` Request for Answer Clarification by jumpstart-ga on 07 Apr 2005 00:32 PDT ```Sounds good ! See you around leapinglizard. -jumpstart```
 Reason this answer was rejected by jumpstart-ga: ```Dear LeapingLizard, First of all, I appreciate for your taking time to explain me the answer... However, I've asked for the refund as some of the *MAJOR* errors in your explanation made me have a *BAD* day :( I am sorry that there was no time for asking clarification and hearing back from you as I was needing it ASAP...as I mentioned in my Question. Just a word of thought, There is no need for clarification again. In case if you feel, that you can clarify and re-post some of the following issues before this question gets closed, that might really help someone in future, who might refer to it :) <<<>>> ---- """"The claim says, in effect, that no path P_tau(v) can possibly cost more than the path P(v) computed by DAD(G,T) in the original graph. To see why this is so, consider that the path P(v) consists of k hops with costs c_1, c_2, ..., c_k. By definition, the sum of these costs is no greater than the delay threshold T. c_1 + c_2 + ... + c_k <= T"""" ---- The paper never mentioned that sum of the <<>> is no greater than the delay threshold T. It should probably be delay...I guess ---- """"If we take the same path through the tau-scaled graph G_tau, each of these costs is multiplied by tau/T and truncated to an integer. In other words, we take the floor of tau/T*c_i for each i from 1 to k. Hence, each cost in the tau-scaled graph is no greater than T/T*c_i. floor(tau/T*c_1) + floor(tau/T*c_2) + ... + floor(tau/T*c_k) <= tau/T*c_1 + tau/T*c_2 + ... + tau/T*c_k = tau/T * (c_1 + c_2 + ... + c_k) <= tau/T * T = tau"""" ---- Again, costs never get multiplied by tau/T....or truncated and so on and so-forth... Also,....."""Hence, each cost in the tau-scaled graph is no greater than <<<>>"""" [should be tau/T*c_i] ---- """"The cost of the path P(v) in the tau-scaled graph G_tau is therefore no greater than tau. But if P_tau(v) is the cheapest path whose delay does not exceed tau, then the cost of P_tau(v) cannot be greater than that of P(v), which is itself a path whose delay does not exceed tau."""" ---- This is again wrong.....as it talks about cost..."The cost of the path <<>> [I guess, it should be P_tau(v) ] in the tau-scaled graph G_tau is therefore no greater than tau" """which is itself a path whose delay does not exceed tau.""" which is totally misleading!! ---- """"Consider that the path P_tau(v) consists of j hops such that j <= D, and name the costs of the hops d_1, d_2, ..., d_j, so that the total cost of P_tau(v) in the tau-scaled graph G_tau is the following."""" ---- Again, it should be delays, instead of costs. ---- """"Now observe that each term T/tau*(d_i+1) is at least as great as the corresponding cost c_i in the original graph G."""" ---- Same error! ---- """"The theorem then stipulates that tau >= D/e, with the following consequence for the cost of P_tau(v) in G."""" ---- Why suddenly D/e? where does that come from? Also, """consequence for the cost of P_tau(v) in"""....should be delay ---- = 4*m * tau_0*2^(k-1) < 4*m * D/e ---- What happened to the k value ? How the paper says k = ceil (log [d/e]/tau_0) ? How all of a sudden tau_0*2^(k-1) < D/e ?? And, the answer to the question number 2 is surely above average but not that much satisfactory! I understand that confusing between delay and costs everywhere in your answer is not that big a deal, if I already knew that's what going on. But, still you must realize this is DSA's complexity, which is basically DELAY SENSITIVE ALGORITHM and that makes its true explanation more important. I didn't really mean to get the full refund. I wanted to give at least half the price for your answer, and I came to know that every refunded answer gets 50% to the researcher however. Anyways, I am totally sorry!! Just thought that you should know...the reasons.. Once again, thanks for all your hard work and please don't mistake me! -JumpStart```