Skyline solution (18.3 in sampler) time complexity

#1

Hello,

I’m a little dumbfounded to see the time complexity for the given solution is described as O(n) when I would expect it to be O(n log n). I was hoping somebody here could help me see the light.

The input (n) is recursively divided in halves and merged. Each merge operation takes linear time and their input size halves at deeper recursion levels but the number of merge operations doubles at at the same time, effectively taking O(n) at each depth level of the recursion tree. Since we keep recursing log n times I understand it as n log n.
What am I missing?

Thanks

0 Likes
#2

Hey Yann,

First of all, thanks for your interests to our book, and we hope you enjoy the sampler like rest of our readers.

I just checked Problem 18.3 in sampler but I hardly see the similarity between the solution in sampler, which uses a linear scan, and the divide-and-conquer like approach you mentioned. Could you double check again with the solution you see in sampler since the solution you mentioned looks like merging skyline problem, which is another problem in our book but definitely not 18.3 in sampler.

Thanks!

0 Likes
#3

Whoops!
You’re right I got confused: I actually have a full copy at hand but when I decided to ask my question I tried to do the right thing by referencing the more up to date sampler instead so that everybody would be on the same page. So I did a word search for skyline and got to 18.3 which had the exact same drawing so I thought it was the same one.

So, moving on, I am indeed referring to the skyline merging problem which is 15.1 for my book. It’s the first problem in the Meta-Algorithms chapter. I can copy and paste the whole problem and solution here if it helps.

Thanks again : )

0 Likes
#4

Hey Yann,

First of all, thanks for your question. and I think you are referring to the problem of drawing skyline. About that problem, O(n) time complexity in the text actually refers the merge procedure but not the whole algorithm. In the later version, we do have a sentence explaining the complexity of this algorithm is O(nlogn) by saying “The time complexity T(n) satisfies the recurrence T(n) = 2T(n/2) + O(n), where the latter term comes from the merge step. This solves to T(n) = O(n log n).”

Please let us know if you have any problem.

0 Likes
#5

Right, I see what you mean, that makes perfect sense.
Thank you for taking the time to answer that, I appreciate it very much : )

0 Likes