Time Complexity for Merge Intervals Algorithm

1. Sorting Step:

   • The first operation in the code is sorting the intervals array based on the start times.
   • Time Complexity of Sorting: The sorting step takes O(n \log n), where n is the number of intervals. This is due to the use of a comparison-based sorting algorithm such as Timsort.

2. Merging Step:

   • The for-loop iterates through each interval exactly once, performing O(1) operations for each iteration to check for overlaps and merge intervals if necessary.
   • Time Complexity of the Loop: The loop runs in O(n) because it processes each of the n intervals once.

Overall Time Complexity:

• The overall time complexity is dominated by the sorting step: O(n \log n)

Space Complexity for Merge Intervals Algorithm

1. Space for Sorting:

   • The sorting has a space complexity of O(\log n) due to the use of in-place sorting for primitive types.

2. Auxiliary Space for Merging:

   • The merged list is used to store the merged intervals. In the worst case, if there are no overlapping intervals, the list will store all n intervals, resulting in O(n) space.

3. Output Array:

   • The toArray() method creates a new array to return the result, which also takes O(n) space.

Overall Space Complexity:

• The total space complexity is: O(n) The primary contributor to space usage is the List used for storing merged intervals and the output array.

2. Problem: Maximum Path Sum in a Binary Tree

Problem Statement: Given a non-empty binary tree, find the maximum path sum. The path may start and end at any node in the tree.

Time Complexity for Maximum Path Sum in a Binary Tree

1. Recursive Calls:

   • The function findMaxPath(TreeNode node) is called recursively for each node in the tree.
   • Number of Calls: Each node in the tree is visited exactly once during the traversal.
   • Overall Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is processed once, making the traversal linear in relation to the number of nodes.

2. Operations per Node:

   • For each node, the following operations are performed:
     • Calculating leftMax and rightMax using recursive calls → O(1) for each operation.
     • Calculating maxSum by comparing and updating → O(1).
     • Returning the result for the current node → O(1).
   • The total work done at each node is constant, O(1), so the time complexity remains O(n) as each node is visited once.

Space Complexity for Maximum Path Sum in a Binary Tree

1. Recursive Call Stack:

   • The space complexity due to recursion depends on the maximum depth of the tree (i.e., the height h).
   • Balanced Tree: For a balanced tree, the height is O(\log n).
   • Unbalanced Tree (Skewed): In the worst case (e.g., a tree that behaves like a linked list), the height is O(n).

2. Auxiliary Space:

   • No additional data structures are used that depend on the size of the input, aside from the recursion stack.

Overall Space Complexity:

• Best Case (Balanced Tree): O(\log n)
• Worst Case (Unbalanced Tree): O(n)

3. Problem: Fractional Knapsack (Greedy Algorithm)

Problem Statement: Given the weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You can take fractions of items.