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.