Hello! I was talking to a friend yesterday who was studying for a programming interview and trying to learn some algorithms basics.
The topic of quadratic-time vs linear-time algorithms came up, I thought this would be fun to write about here because avoiding quadratic-time algorithms isn’t just important in interviews – it’s sometimes good to know about in real life too! I’ll explain what a “quadratic-time algorithm is” in a minute :)
here are the 3 things we’ll talk about:
quadratic time functions are WAY WAY WAY slower than linear time functions
sometimes you can make a quadratic algorithm into a linear algorithm by using a hashmap
this is because hashmaps lookups are very fast (instant!)
I’m going to try to keep the math jargon to a minimum and focus on real code examples and how fast/slow they are.