# Analysis

### Complexity

The Fractional Knapsack Problem is known for its efficient solution, thanks to the greedy algorithm that it employs. Here's a breakdown of the space and time complexities of the matching engine algorithm:

**Time Complexity:** The greedy algorithm used to solve the Fractional Knapsack Problem has a time complexity of O(n log n), where n is the number of items to be considered. The most time-consuming step is often sorting the items based on their price-to-amount ratios, which requires O(n log n) time when using a standard sorting algorithm. After the sorting step, the algorithm typically completes in linear time (O(n)) as it iterates through the sorted list of items to select the optimal fractional parts.

**Space Complexity:** The space complexity of the Fractional Knapsack Problem's greedy algorithm is O(n). This is primarily due to the need to store the sorted list of items and the corresponding price-to-amount ratios in memory. The space required for other variables and data structures used in the algorithm is typically negligible compared to the space required for storing the input data.

### Gas cost analysis

Average gas cost for matching order is from 120,000 ~ 250,000. the gas cost might be higher as user configures matching iteration to be more than 5.

Last updated