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
?
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.