educative.io

All-paths-for-a-sum- How's time complexity O(N^2)

Courses
,
#1

How’s the time complexity for every leaf node to store its path which will take O(N)? We are just appending in the list, aren’t we?

#2

Hi, I have the same question and hope the author can clear the confusion here

#3

To store the path, we are making a copy of the current path, which will take O(N). Here is the relevant line for Java (here currentPath is a list):

allPaths.add(new ArrayList(currentPath));

For Python:

allPaths.append(list(currentPath))

#4

@Design_Gurus, can you clarify why this is N * N, instead of just N + N? Intuitively, N * N seems too big for only traversing and making a copy. What am I missing?

1 Like
#5

You may make a copy on each leaf node, which are max N / 2. So, O(N / 2 * N) = O(N^2)