DEV Community

loading...

Discussion on: Advent of code: 2020 Day 01

Collapse
annisalli profile image
Anniina Sallinen

Thank you for your solutions! I like your solution to part 1 especially, I implemented it first with brute force but then ended up optimizing it, but I still only got O(n log n) performance with sorting the list and then performing binary search. Your solution is a bit simpler and more elegant 😄

For your question about optimizing by never looking into any combination twice, I think it's still O(n^2) because although in practice we go through less elements, the amount of iterations still increases fast when n increases.

So if we have a list of five numbers we have to iterate 4+3+2+1 elements (10 in total). With 10 elements there are 45 iterations, with 20 there are 190 and so on. With 200 elements it's already 19 900 iterations. This can also be expressed as arithmetic sequence: 1+2+3+4+...+n. I had the intuition that the optimization like that doesn't matter, but I couldn't convince myself at first so I draw two plots with python.

This is a picture of growth without the optimization:
Slower way

This is a picture of growth with the optimization:
Faster way

As you can see, the growth is still as fast. I wanted to have some kind of formal proof for that as well, so that's when I googled it and found this stack overflow question and answer: stackoverflow.com/a/44255732 😊

This is of course the case for the part 1 only, I didn't have time to think through how the optimization affects the performance of part 2!

Collapse
cnille profile image
Christopher Nilsson Author

Thanks Anniina for your comment! Great with the visuals and the stack-overflow link. My key take-away is then that the extra keystrokes required to implementing "never check same twice" is not worth haha :)

Oh nice with using sorting and binary search! Seems that python's built-in sort uses timsort which has worst case O(n log(n)). So that would be easy for me to add. How did you solve the binary search part in this puzzle? :)

Collapse
annisalli profile image
Anniina Sallinen

Haha yeah well in practice it's faster, but the time complexity is still the same.

I just wrote a blog post about different solutions to the puzzle and their time complexities, you can check my sort + binary search solution from the post if you like: dev.to/annisalli/understanding-tim... 😊 The sort + binary sort is still less optimal than your solution with set, but it was fun to implement it!