Know the complexity of the algorithms

This article talks about runtime and memory usage of most algorithms used in computer science. In the past, when I was getting ready for an interview, I spent a lot of time researching the Internet to find information about the best, average and worst case of search and sorting algorithms so that the question asked at the interview did not baffle me. Over the past few years, I have been interviewed at several startups from Silicon Valley, as well as at some large companies such as Yahoo, eBay, LinkedIn and Google, and every time I prepared for the interview, I thought: “Why didn’t anyone create a good cheat sheet for asymptotic complexity of algorithms? ". To save your time, I created such a cheat sheet. Enjoy it!

Search

Sorting

Data structures

Heaps

Graph view

Let a graph with | V | vertices and | E | ribs then

Asymptotic growth notation

1. (O - large) is the upper bound, while (Omega - large) is the lower bound. Theta requires both (O - large) and (Omega - large), so it is an accurate estimate (it should be limited both from above and from below). For example, an algorithm requiring Ω (n logn) requires at least n logn time, but the upper bound is not known. An algorithm requiring Θ (n logn) is preferable because it requires at least n logn (Ω (n logn)) and no more than n logn (O (n logn)).
2. f (x) = Θ (g (n)) means that f grows like g when n tends to infinity. In other words, the growth rate f (x) is asymptotically proportional to the growth rate g (n).
3. f (x) = O (g (n)). Here the growth rate is not faster than g (n). O big is most useful because it represents the worst case.

In short, if an algorithm has complexity __ then its efficiency is __

O growth chart - large