I don’t really understand time complexity, and wanted some clarification in this hypothetical situation.
If I were being given items one by one, and I wanted a list of them all in the reverse order I got them in, I could add each item to an ArrayList, then reverse it. Both of these operations are O(n) in time complexity, and therefore my total is O(2n), which is just O(n).
However, I could also add each item as I got it to a Stack, and since Stacks are LIFO, it’s already reversed once I have all of the items. This skips the O(n) ArrayList reversing, but is still O(n) overall since getting the n items was O(n).
I think the second option would be better, since I’m avoiding an O(n) subroutine, but how can I say that I have made my algorithm more efficient?
In the context of explaining how my second algorithm is more efficient, is it appropriate to just say I have made it more efficient by removing an O(n) subroutine?