Time and space complexity analysis (big-O notation)

Course Curriculum

Chapter 1: Complexity analysis basics

Lecture 1: Introduction

Lecture 2: Examples

Lecture 3: Big-O, big-Ω, and big-θ notations

Lecture 4: Extra resource: Notations mathematical definition

Lecture 5: Best, average, and worst case

Lecture 6: Complexity classes

Chapter 2: How to analyze the complexity of an algorithm

Lecture 1: Complexities hierarchy

Lecture 2: How to analyze the complexity of an algorithm

Lecture 3: Amortized complexity

Lecture 4: How to compare two algorithms

Lecture 5: "Find pair that sums up to k" problem analysis

Chapter 3: Searching algorithms and complexity analysis

Lecture 1: Linear search algorithm

Lecture 2: Binary search algorithm

Lecture 3: Knuth-Morris-Pratt (KMP) algorithm

Chapter 4: Sorting algorithms and complexity analysis

Lecture 1: Introduction

Lecture 2: Insertion sort

Lecture 3: Bubble sort

Lecture 4: Selection sort

Lecture 5: Merge sort

Lecture 6: Heapsort

Lecture 7: Quicksort

Lecture 8: Counting sort

Lecture 9: Radix sort

Lecture 10: Bucket sort

Lecture 11: Shell sort

Lecture 12: Extra resource: Summary

Chapter 5: Recursive functions and complexity analysis

Lecture 1: Introduction

Lecture 2: Recursion tree method

Lecture 3: Recurrence relation method

Lecture 4: Master theorem method

Lecture 5: Space complexity analysis of recursive functions

Lecture 6: Memoization

Lecture 7: Dynamic programming

Chapter 6: Data structures and complexity analysis

Lecture 1: Arrays

Lecture 2: Linked lists, stacks, and queues

Lecture 3: Hash tables and sets

Lecture 4: Trees

Lecture 5: Mathematical proof of time complexity of building a binary heap

Lecture 6: Graphs

Lecture 7: Extra resource: Summary

Chapter 7: Common mistakes and misconceptions

Lecture 1: Nested loops == O(n²)?

Lecture 2: Common mistakes

Lecture 3: Do we always need to optimize?

Chapter 8: Practice: complexity analysis of popular coding interview problems solutions

Lecture 1: First repeating character

Lecture 2: Maximum subarray

Lecture 3: Peak finding

Lecture 4: Palindrome linked list

Lecture 5: String subsequences

Lecture 6: Minimum cost path

Lecture 7: Longest consecutive sequence

Lecture 8: Longest common subsequence

Lecture 9: Subsets that sum up to k

Lecture 10: Balanced binary tree

Lecture 11: Array permutations

Lecture 12: Word search

Lecture 13: N-queens

Lecture 14: Bonus: space-optimized dynamic programming