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

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. Formal Analysis Tools - Functions and Their Growth This lesson discusses the building blocks for analyzing algorithms. Basics - Problem Set 1 Practice problems to hone analysis skills. 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 Basics - Introduction This chapter lays the groundwork for the material covered in the course and sets out the expectations for the readers. 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. Recursive - Problem Set 3 Questions to understand recursive complexity analysis 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. Recursive - Binary Search - Recursive Implementation This chapter details the reasoning behind binary search’s time complexity Recursive - Recurrence Part II This chapter continues the discussion on analyzing the complexity of recursive algorithms. Recursive - Permutations This chapter shows how one can reason about recursive problems without extensive mathematical knowledge Formal Analysis Tools - Problem Set 2 Practice problems relating to analysis notations. Recursive - Recurrence This chapter introduces recursive algorithms and how they can be analyzed. Probabilistic Analysis - The Tinder Problem This lesson discusses a sample problem and works out the complexity using probabilistic analysis. Probabilistic Analysis - Expected Value of a Random Variable This chapter discusses the expected values of random variables and how to calculate them. Amortized Analysis - Solution Set 5 Solutions to problem set 4 Amortized Analysis - Fancy Stack In this chapter, we discuss the complexity of various operations of a stack which supports a multipop operation. Probabilistic Analysis - Quantifying Chance & Randomness This chapter discusses pre-requisite concepts for undertaking probabilistic analysis. Probabilistic Analysis - Random Variables This chapter discusses random variables. Recursive - Solution Set 3 Solutions to problem set 3 Amortized Analysis - Dynamic Array This chapter discusses the time complexity of insert operations on a dynamic array. Amortized Analysis - Problem Set 5 Questions to practice amortized analysis. Probabilistic Analysis - Probability Distribution This chapter discusses the concept of probability distribution. Complexity Theory - Between P and NP ? Do any problems exist that aren’t NP-complete and not in P? Complexity Theory - Problem Set 6 Questions to test understanding of P/NP problems. The End - Epilogue Have questions about Epilogue? Go for it! 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. Basics - Analyzing Algorithms We start our journey into the world of complexity by analyzing the insertion sort algorithm. Formal Analysis Tools - Theta Notation We formally introduce theta notation, which forms the basis of mathematical analysis of algorithms. Recursive - Top Down and Bottom Up Approaches This chapter continues the discussion on the complexity of dynamic programming problems. Formal Analysis Tools - Solution Set 2 Solutions to problem set 2. Complexity Theory - Why should I bother? This chapter gives an introduction to complexity theory. Complexity Theory - P and NP classes In this lesson, we discuss the two most important complexity classes P and NP. Formal Analysis Tools - Big O and Big Omega Notations Discusses the Big O notation with examples Data-Structures - Linked List This lesson discusses the complexity of operations on a linked list. Data-Structures - Array This lesson talks about the complexity of operations on an array. Data-Structures - Hash Table This chapter discusses operations on hash tables. Data-Structures - Doubly Linked List This section explores operations on a doubly linked list Data-Structures - Stacks and Queues This lesson talks about operations on stacks and queues. Data-Structures - Solution Set 4 Solutions to problem set 4. Data-Structures - Problem Set 4 Have questions about Problem Set 4? Go for it! Data-Structures - Tree Structures This lesson is a general discussion on reasoning about space and time complexity of tree structures Complexity Theory - Get Rich with Complexity In this lesson, we discuss the famous is P=NP dilemma. The End - Cheat Sheet This is a compilation of worst-case complexities for various data-structures and algorithms. Amortized Analysis - Cost Over Sequence of Operations This chapter introduces the reader to aggregate analysis of algorithms. Formal Analysis Tools - Small omega and Small o Notations In this lesson, we discuss notations which imply loose bounds.