computational complexity

How slow can you go?

What are we Counting? 🍎🍊🍐 So if we have two pieces of code, how do we know which piece of code will be “faster”? Yeah sure we can run the two of them side by side, but how fast code runs depends on a lot of factors, such as what device it was run on and what other programs were running at the same time.

Hijacked Notation Like many things in computer science, Big $O$ has a very specific definition and has a use case designed for number theory. Computer Scientists then took that notation, changed nothing about the notation, and then proceeded to use it in whatever way they felt was convenient1.

Why Do Mathematicians Do Something Different? In case my salty ranting on the previous page couldn’t clue you in, I will now take the time to explain what the notation of $\mathcal{O}, \Omega, \Theta$ truly mean in mathematics.

A Victim of my Own Design Prior, we have been working on very nice and fun programs that have been super straightforward to do counting on, but many algorithms that are taught in classes are self referential and recursive.

The Best You Can Get Prove why n log(n) is the best comparison based sorting algorithm Whats Up With QuickSort? Prove why quicksort is n log(n)