| Algo Name | Time Complexity | Auxiliary Space | |
|---|---|---|---|
| Average Case | Worst Case | ||
| Slow Convex Hull | O(n3) | O(n3) | O(n) |
| Kirkpatrick–Seidel | O(nlogH) | O(nlogH) | O(n) |
| Jarvis’ Algorithm | O(nH) | O(n2) | O(n) |
We have observed significant efficiency gains with both of the algorithms we've implemented compared to the brute force approach (i.e., Slow Convex Hull). Even for relatively small values of n, the time taken is considerably reduced. However, when comparing the Jarvis and KPS algorithms, the time taken is nearly equivalent for smaller n values, making the choice between them less critical in those cases.
However, as n increases, the superiority of the KPS algorithm becomes evident, with its efficiency outpacing that of the Jarvis algorithm. This trend is clearly illustrated in the graphs we have plotted.