Skip to content

Latest commit

 

History

History
10 lines (9 loc) · 736 Bytes

README.md

File metadata and controls

10 lines (9 loc) · 736 Bytes

DB2-Skyline-Challenge

Data Bases 2 Skyline Challenge - a.a. 2022-2023
Professor: Davide Martinenghi

The challenge

The skyline algorithms we saw in class are inherently quadratic in the size of the dataset, but can we achieve sub-quadratic complexity (i.e., an overall complexity that is less than O(N²), where N is the dataset size)? Just focus on the 2-dimensional case and either

  1. Prove that no sub-quadratic algorithm can correctly compute the skyline in 2D, or
  2. Code (in a language of your choice) a correct algorithm that computes the skyline in 2D with sub-quadratic complexity.

Here is my solution in O(NlogN) that granted me 2 out of 2 extra points