I am having trouble understanding Big-O notation. How do I find the Big-O and worst case running time of this function?

I wrote this function to reverse the order of a doubly linked list.

public void reverse() { Node<T> temp = head; Node<T> current = head.next; head.next = null; head.previous = current; while(current != null) { Node<T> next = current.next; current.next = temp; current.previous= next; temp = current; current = next; } head = tail;
}

1

2 Answers

Look for the number of nested loops.

Since there isn't one it's just O(n) because there's no geometric reduction of the n over the course of the loop

The "data structure" should remind us of a "doubly linked list", and assuming a list of size n, this algorithms reverses the order of the list. We can count now the (compare, assign, mathematical) operations, which this algorithm will accomplish (besides, whether it is correct & terminates) ..in relation to n:

And we will find, that this algorithm does (in worst, best & average (so every)) case:

4 assign statements: Node<T> temp = head; Node<T> current = head.next; head.next = null; head.previous = current;
n + 1 compare statements: while(current != null)
(lets not count the braces))
n * 5 assign operations: Node<T> next = current.next; current.next = temp; current.previous= next; temp = current; current = next;
and 1 last assign operation head = tail;

so it is 4 + n + 1 + 5 * n + 1 = 6 * n + 6 (assign or compare ... but compare are the "most expensive" ones in terms of run time) operations. We eliminate constant factors and offset (since they can be neglected, when ngets big...and due to exact mathematical rules, we learned), and get:

6n + 6 = O(n)

..and apropos: it is correct & terminates! ;)