Run-time complexities for recursive algorithms
Run-time complexities for recursive algorithms
I've searched high and low and can't seem to find a lot of material related to run-time complexities, recursion, and java.
I'm currently learning run-time complexities and Big-O notation in my Algorithms class, and I'm having trouble analyzing recursive algorithms.
private String toStringRec(DNode d) { if (d == trailer) return ""; else return d.getElement() + toStringRec(d.getNext()); }
This is a recursive method that will simply iterate though a doubly-linked list and print out the elements.
The only thing I can come up with is that it has a run-time complexity of O(n), since the number of recursive method calls will depend on the number of nodes in the DList, but I still don't feel comfortable with this answer.
I'm not sure whether I should be accounting for the addition of d
and d.getNext()
.
Or am I just completely off track and the run-time complexity is constant, since all its doing is retrieving elements from the DNodes
in the DList
?
Answer by sgmorrison for Run-time complexities for recursive algorithms
The algorithm has run-time complexity of O(n) as you suggest. Your list has n items in it, and the algorithm will do a near-fixed amount of work for each item (that work being Element and Next access, plus a new toStringRec call). Retrieving an Element from a DNode takes constant time, and constant times are discarded in big-O notation.
The interesting thing about recursive methods (in most cases) is that they are also O(n) in space complexity too. A new stack entry (to store the parameters passed to the method) is created for each call to toStringRec, which is called n times.
Answer by dasblinkenlight for Run-time complexities for recursive algorithms
At the first glance, this looks like a classic case of tail recursion modulo cons, a generalization of tail call. It is equivalent to a loop with the number of iterations.
However, it is not that simple: the tricky thing here is the addition of d.getElement()
to a growing string: this is in itself a linear operation, and it is repeated N
times. Hence the complexity of your function is O(N^2)
.
Answer by Adrian Panasiuk for Run-time complexities for recursive algorithms
If T(n) is the number of elementary operations (in this case - when we enter the body of the function, any of the lines inside are executed at most once and all but the second return is not O(1)) executed by calling toStringRec on a list of n elements, then
T(0) = 1 - as the only things that happen is the branch instruction and a return T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the function besides calling toStringRec is some constant time stuff and concatenating strings that takes O(n) time; and we also run toStringRec(d.getNet()) which takes T(n-1) time
At this point we have described the complexity of the algorithm. We can now compute the closed form for T, T(n) = O(n**2).
Answer by cjm for Run-time complexities for recursive algorithms
This is a pretty simple example, but the trick is to define a recurrence relation, which is a function of the runtime of a given input size in terms of smaller input sizes. For this example, assuming that the work done at each step takes constant time C and assuming that the base case does no work, it would be:
T(0) = 0 T(n) = C + T(n-1)
You can then solve for running time using substitution to find a series:
T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC
By the definition of O, this equation is O(n). This example isn't particularly interesting, but if you look at something like the runtime of mergesort or another divide and conquer algorithm you can get a better idea of recurrence relations.
Answer by MMS for Run-time complexities for recursive algorithms
For such recursive algorithms, it's usually possible to write a recursive equation to calculate the order. It's customary to show number of instructions executed with T(n). In this example, we have:
T(n) = T(n - 1) + O(1)
(Supposing that the function getElement
runs in constant time.) This equation's solution is trivially T(n) = O(n).
That was the general case. However, sometimes you can analyze the algorithm without writing such equation. In this example, you can easily argue that each element is accessed at most once, and each time some constant time work is done; so, it takes O(n) overall to do the job.
Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72
0 comments:
Post a Comment