# 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/collection/page/5307417243942912/5630721452408832/5686306919153664). Basics - Problem Set 1 Practice problems to hone analysis skills. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5649391675244544). 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/collection/page/5307417243942912/5630721452408832/5740423507083264). Recursive - Binary Search - Recursive Implementation This chapter details the reasoning behind binary search's time complexity View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5682617542246400). 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/collection/page/5307417243942912/5630721452408832/5637489247125504). Recursive - Recurrence This chapter introduces recursive algorithms and how they can be analyzed. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5671321778257920). 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/collection/page/5307417243942912/5630721452408832/5632984900173824). Probabilistic Analysis - Quantifying Chance & Randomness This chapter discusses pre-requisite concepts for undertaking probabilistic analysis. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5206978905243648). 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/collection/page/5307417243942912/5630721452408832/5745060998021120). Amortized Analysis - Problem Set 5 Questions to practice amortized analysis. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5691726094139392). Recursive - Solution Set 3 Solutions to problem set 3 View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5726683906703360). Complexity Theory - Problem Set 6 Questions to test understanding of P/NP problems. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5686683802533888). 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/collection/page/5307417243942912/5630721452408832/5654153720233984). 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/collection/page/5307417243942912/5630721452408832/5640471028170752). 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/collection/page/5307417243942912/5630721452408832/5694639155707904). Formal Analysis Tools - Functions and Their Growth This lesson discusses the building blocks for analyzing algorithms. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5699127396532224). Formal Analysis Tools - Problem Set 2 Practice problems relating to analysis notations. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5714163003293696). Probabilistic Analysis - Random Variables This chapter discusses random variables. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5753341694967808). 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/collection/page/5307417243942912/5630721452408832/5720605454237696). The End - Epilogue Have questions about Epilogue? Go for it! View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5644572721938432). Data-Structures - Linked List This lesson discusses the complexity of operations on a linked list. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5631242217193472). Formal Analysis Tools - Big O and Big Omega Notations Discusses the Big O notation with examples View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5718532058775552). Data-Structures - Array This lesson talks about the complexity of operations on an array. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5762702576189440). Data-Structures - Stacks and Queues This lesson talks about operations on stacks and queues. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5667766619078656). Data-Structures - Problem Set 4 Have questions about Problem Set 4? Go for it! View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5725722907770880). 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/collection/page/5307417243942912/5630721452408832/5736754531270656). Recursive - Recurrence Part II This chapter continues the discussion on analyzing the complexity of recursive algorithms. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5769928858664960). Recursive - Problem Set 3 Questions to understand recursive complexity analysis View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5746311907246080). Recursive - Permutations This chapter shows how one can reason about recursive problems without extensive mathematical knowledge View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5760820306771968). 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/collection/page/5307417243942912/5630721452408832/5182111044599808). 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/collection/page/5307417243942912/5630721452408832/5647906690301952). 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/collection/page/5307417243942912/5630721452408832/6435193084706816). Amortized Analysis - Solution Set 5 Solutions to problem set 4 View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5630110493310976). Complexity Theory - Why should I bother? This chapter gives an introduction to complexity theory. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5704147139559424). 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/collection/page/5307417243942912/5630721452408832/5670405876482048). 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/collection/page/5307417243942912/5630721452408832/5767494685949952). 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/collection/page/5307417243942912/5630721452408832/5159696684023808). 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/collection/page/5307417243942912/5630721452408832/5635415851663360). 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/collection/page/5307417243942912/5630721452408832/5765785288966144). 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/collection/page/5307417243942912/5630721452408832/5123733849112576). Data-Structures - Doubly Linked List This section explores operations on a doubly linked list View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5739578472267776). Data-Structures - Hash Table This chapter discusses operations on hash tables. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5706971080556544). Data-Structures - Solution Set 4 Solutions to problem set 4. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5686003050217472). 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/collection/page/5307417243942912/5630721452408832/5706033703944192). Formal Analysis Tools - Solution Set 2 Solutions to problem set 2. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5728757302165504). Probabilistic Analysis - Probability Distribution This chapter discusses the concept of probability distribution. View the lesson [here](https://www.educative.io/collection/page/5307417243942912/5630721452408832/5646620347596800). 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/collection/page/5307417243942912/5630721452408832/5666313846390784).