# Big-O Notation For Coding Interviews and Beyond (C. H. Afzal)

Amortized Analysis - Dynamic Array This chapter discusses the time complexity of insert operations on a dynamic array. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/JYPmOo39Bql). Basics - Introduction This chapter lays the groundwork for the material covered in the course and sets out the expectations for the readers. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/JYlM1noxJ9o). Recursive - Dynamic Programming This chapter works on a sample dynamic programming problem to show how complexity for this class of problems can be worked out. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m2q8RqrmKO3). Probabilistic Analysis - Quantifying Chance & Randomness This chapter discusses pre-requisite concepts for undertaking probabilistic analysis. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/mE6pmwrRwp0). Probabilistic Analysis - Expected Value of a Random Variable This chapter discusses the expected values of random variables and how to calculate them. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/JYlLJB6DK7g). Amortized Analysis - Fancy Stack In this chapter, we discuss the complexity of various operations of a stack which supports a multipop operation. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/NELZVKV53Bm). Amortized Analysis - Problem Set 5 Questions to practice amortized analysis. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m22Y19LlrE3). Basics - Problem Set 1 Practice problems to hone analysis skills. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gxnn6KylLor). Recursive - Binary Search - Recursive Implementation This chapter details the reasoning behind binary search's time complexity View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gxkNX8WvDBk). Basics - Need for Speed This chapter discusses analogies from real life to draw a parallel between algorithmic complexity and comparisons we make in day to day situations. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVQm8j5ZmK7). Data-Structures - Tree Structures This lesson is a general discussion on reasoning about space and time complexity of tree structures View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVlxqvG4E33). Formal Analysis Tools - Problem Set 2 Practice problems relating to analysis notations. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVAvlqLZnO0). Complexity Theory - Between P and NP ? Do any problems exist that aren't NP-complete and not in P? View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVMVLr6z3pR). The End - Epilogue Have questions about Epilogue? Go for it! View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/YQ73Mrg3Dz2). Data-Structures - Linked List This lesson discusses the complexity of operations on a linked list. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/RMOQrM3zKYY). Data-Structures - Array This lesson talks about the complexity of operations on an array. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/7nVnXoNrl4B). Data-Structures - Stacks and Queues This lesson talks about operations on stacks and queues. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/xV1NJM7OE4n). Data-Structures - Problem Set 4 Have questions about Problem Set 4? Go for it! View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/3jKmJ87V25M). Recursive - Problem Set 3 Questions to understand recursive complexity analysis View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/3jE1ZQyKYOr). Recursive - Recurrence Part II This chapter continues the discussion on analyzing the complexity of recursive algorithms. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/B89q35D85No). Probabilistic Analysis - The Tinder Problem This lesson discusses a sample problem and works out the complexity using probabilistic analysis. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/q2pg1wJN4yR). Data-Structures - Priority Expiry Cache Problem We'll walk through an actual phone screen question asked at Tesla in this lesson. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/B1pL2j2vl3Q). Amortized Analysis - Solution Set 5 Solutions to problem set 4 View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/YQWGjlZZVz9). Complexity Theory - Why should I bother? This chapter gives an introduction to complexity theory. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/NE7k4WpKl9m). Complexity Theory - P and NP classes In this lesson, we discuss the two most important complexity classes P and NP. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m2ypOkKPm4n). Formal Analysis Tools - Big O and Big Omega Notations Discusses the Big O notation with examples View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVMjy1O96Gp). The End - Cheat Sheet This is a compilation of worst-case complexities for various data-structures and algorithms. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qVLk26yvZy3). Recursive - Recurrence This chapter introduces recursive algorithms and how they can be analyzed. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/JYQpVMg6MLy). Recursive - Solution Set 3 Solutions to problem set 3 View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/B8RJXPrVwVx). Data-Structures - Hash Table This chapter discusses operations on hash tables. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gx77OPgwmMr). Data-Structures - Solution Set 4 Solutions to problem set 4. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/RMLzWp8G2WO). Amortized Analysis - Cost Over Sequence of Operations This chapter introduces the reader to aggregate analysis of algorithms. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/q28DnjLq8xy). Formal Analysis Tools - Theta Notation We formally introduce theta notation, which forms the basis of mathematical analysis of algorithms. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/B8rPjvpO20N). Data-Structures - Doubly Linked List This section explores operations on a doubly linked list View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/YQ09Gy8BoQW). Basics - Analyzing Algorithms Part II In this lesson, we'll dry run insertion sort and count the instructions executed on an array of length 5. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m27yx8vJ0Dr). Basics - Analyzing Algorithms We start our journey into the world of complexity by analyzing the insertion sort algorithm. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m220RR1ZNVp). Formal Analysis Tools - Functions and Their Growth This lesson discusses the building blocks for analyzing algorithms. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/NEEwx6Y7M1m). Recursive - Permutations This chapter shows how one can reason about recursive problems without extensive mathematical knowledge View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/NEW9pyy0XM2). Formal Analysis Tools - Solution Set 2 Solutions to problem set 2. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/m2MJD192GN9). Complexity Theory - Get Rich with Complexity In this lesson, we discuss the famous is P=NP dilemma. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/xV9jYOVOkQJ). Complexity Theory - NP-Complete and NP-Hard In this chapter we further the discussion on complexity theory with NP-complete and NP-hard complexity classes. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/7npkAKlq9gw). Complexity Theory - Problem Set 6 Questions to test understanding of P/NP problems. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gxkmLoZwK9Y). Basics - Analyzing Algorithms Part III In this lesson, we will work out a generalization for the number of instructions executed for an array of length n View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/7nXJOk9pY31). Recursive - Top Down and Bottom Up Approaches This chapter continues the discussion on the complexity of dynamic programming problems. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/YM08zoEwKWY). Formal Analysis Tools - Small omega and Small o Notations In this lesson, we discuss notations which imply loose bounds. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gxMKl3W1lM9). Probabilistic Analysis - Probability Distribution This chapter discusses the concept of probability distribution. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/gxpvqPvo06Y). Probabilistic Analysis - Random Variables This chapter discusses random variables. View the lesson [here](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond/qV6nKgkEomG).