Fractional Knapsack Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Fractional Knapsack Problem

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to solve the Fractional Knapsack Problem changes as the number of items grows.

Specifically, we ask: how does the work increase when we have more items to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function fractionalKnapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const items = [];
  for (let i = 0; i < n; i++) {
    items.push({
      weight: weights[i],
      value: values[i],
      ratio: values[i] / weights[i]
    });
  }
  items.sort((a, b) => b.ratio - a.ratio);
  let totalValue = 0;
  let remaining = capacity;
  for (const item of items) {
    if (item.weight <= remaining) {
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      totalValue += item.ratio * remaining;
      break;
    }
  }
  return totalValue;
}
    

This code sorts items by value per weight and then picks as much as possible from the best items until the capacity is full.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the items by their value-to-weight ratio.
• How many times: Sorting runs once over all items, which takes time depending on the number of items.
• Two loops run over all items: one to create the list and one to pick items.

How Execution Grows With Input

As the number of items increases, sorting takes more time, growing faster than just looking at items one by one.

Input Size (n)	Approx. Operations
10	About 10 log 10 (sorting) + 2*10 (loops) = ~40 operations
100	About 100 log 100 + 200 = ~900 operations
1000	About 1000 log 1000 + 2000 = ~13000 operations

Pattern observation: The sorting step dominates and grows faster than the loops, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of items, mainly because of sorting.

Common Mistake

[X] Wrong: "The main time cost is picking items, so the complexity is O(n)."

[OK] Correct: Sorting the items by ratio takes more time than just picking, so sorting dominates the total time.

Interview Connect

Understanding this time complexity helps you explain why sorting is important before choosing items, a key skill in optimization problems.

Self-Check

"What if the items were already sorted by value-to-weight ratio? How would the time complexity change?"