complexity.md

Time Complexity (Big O Time):

The time complexity of this program is O(max(N, M)), where "N" and "M" represent the lengths of the input linked lists l1 and l2, respectively. Here's the breakdown:

1. The program iterates through both linked lists l1 and l2 simultaneously using a while loop. The loop runs as long as either of the two lists has elements to process.
2. Inside the loop, it performs constant-time operations for each node:
   • It calculates the sum of three integer values (constant time).
   • It creates a new node (constant time).
   • It updates pointers and variables (constant time).

Since the loop runs until the end of the longer of the two input linked lists, the overall time complexity is O(max(N, M)), where "N" and "M" are the lengths of l1 and l2, respectively.

Space Complexity (Big O Space):

The space complexity of this program is O(max(N, M)), which is primarily determined by the space used for the output linked list. Here's why:

1. The program creates a new linked list to store the result, and the length of this linked list can be at most max(N, M) + 1 (where +1 is for the potential carry at the end).
2. Other than the output linked list, the program uses a constant amount of space for variables like dummyHead, p, q, curr, and carry.

Therefore, the space complexity is O(max(N, M)).