I have n amount of apples and n amount of bananas which will be paired up in n lunchboxes. Each lunchbox will contain one apple and one banana to feed my n children.

However, the apples and banans has different sizes, making them have different values. I don't want my lunchboxes to have different values so that someone gets more to eat than the other. To solve this, I want to pair upp the apples and bananas in a way that the difference between the most valuable lunchbox, and the least valuable lunchbox is as small as possible.

The total value of a lunchbox is the value of the apple plus the value of the banana.

I want to design an algorithm (pseudocode preferrably pyhton) that finds the smallest possible difference between the most and the least valuable lunchbox, assuming the apples and bananas are paired up optimally.

The input to the algorithm is the values: a₁.....a_n for the n apples and b₁......b_n for the n bananas.

The algorithm only has to find the value, and not report which apple to combine with which banana.

The time complexity must run faster or equal to O(n^1.8), with a unit cost analysis, assuming adding or comparing two values takes O(1) time.

example: if n=4 apples a=(9,14,15,10) bananas=(19,22,19,21) output would be 1

Please name what algorithms are being used and the method, (dynamic programming, knapsack, greedy approach, divide and conquer etc) Please argue for the correctness of the algorithm and give an analysis of the time complexity

Thank you