The ultimate guide to Big-O notation for coding interviews, developed by FAANG engineers. Learn algorithm complexity in simple terms and get interview-ready in just a few hours.

This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond

The small o and small &omega; are complementary notations to the big O and big &Omega; notations. For algorithm analysis, the most important notation is the big O. For the sake of completeness, we mention the small o and small &omega; notations too.

<h2>Small o</h2>

The small o is not an asymptotically tight upper bound. The formal definition is similar to big O, with one important difference. A function f(n) belongs to the set o(g(n)), if the following condition is satisfied.


>$$0 \leq f(n) < cg(n)$$
>$$for\: any\: positive\: constant\: c,\: there\: exists\: some\: constant\: n_0\: which\: if\: n\: surpasses\:,\: the\: above\: inequality\: holds$$ 
Note that the inequality should not hold for some positive constant c, as is the case for big O; rather, it should hold for all positive constants.
Unlike big O, which may or may not be tight, the small o notation is necessarily not tight.

In this lesson, we discuss notations which imply loose bounds.

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Small omega and Small o Notations