0% completed
"The time complexity of the above algorithm is O(N^2), where ‘N’ is the total nu...
hj3yoo
Mar 3, 2022
"The time complexity of the above algorithm is O(N^2), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once (which will take O(N)), and for every leaf node, we might have to store its path (by making a copy of the current path) which will take O(N)."
Can someone explain why storing its path will take O(N) time complexity instead of O(1)? I can understand O(N) space complexity, but why would the time to store an array be proportional to the size of it?
0
0
Comments
Design Gurus4 years ago
Creating a copy of a list with 'N' items takes O(N), since we must iterate the list and make copy of each individual item.
For Java, following line in the solution takes O(N):
allPaths.add(new ArrayList(currentPath));
Design Gurus4 years ago
On this page