Cons lst = null; for (int i = 0; i < n; i++ ) lst = cons( i, lst ); lst = nreverse(lst);
What is the Big O of this code?
The cons is always O(1), inside a loop of n, so the loop is O(n). nreverse is also O(n). O(n) + O(n) = O(n).
Rule: If the order in which you cons up a list makes it come out backwards, nreverse it at the end.
Contents Page-10 Prev Next Page+10 Index