Complexity Theory - Running Time Analysis of Algorithms

Learn Asymptotic Complexity, Running Times Analysis (O, Ω, θ) and Complexity Classes (P and NP)

Created byHolczer Balazs

Last updated 6/2022

English

English [Auto],

What you'll learn

Understand running time analysis
To be able to analyze algorithms' running times
Understand complexity notations
Understand complexity classes (P and NP)

Course content

5 sections • 18 lectures • 1h 55m total length

Introduction0:51
Explore complexity theory and running time analysis, measuring time and notations like big O, Omega, Theta, with case studies on constant, logarithmic, polynomial, and linear running times.

How to measure the running times of algorithms?8:44
Learn to measure running time complexity by counting steps relative to input size, recognize the order of growth (linear, quadratic, exponential), and understand the memory trade-off.
Complexity theory illustration4:21
Compare linear and quadratic running times using concrete sorting examples, showing how input size affects performance and introducing asymptotic analysis for large input sizes.
Complexity notations - big (O) ordo8:11
Define the big O notation and asymptotic analysis to bound an algorithm's running time as input size grows, and illustrate with bubble sort and upper bounds.
Complexity notations - big Ω (omega)4:29
Explore the big omega notation as a lower bound for running time with respect to input size, using a constant and a threshold.
Complexity notations - big (θ) theta2:06
Understand big theta notation as the tight bound for running time, bounding f(n) above and below by constants times g(n) for large n. Relate theta to O and Omega.
Complexity notations - example9:10
Explore concrete examples of running time analysis using big O, Omega, and Theta notations, including f(n)=3n^2-100n+6, to illustrate upper, lower, and tight bounds.
Algorithm running times10:51
Analyze how algorithm running times scale with input size, from constant and logarithmic to linear, linearithmic, polynomial, exponential, and factorial, with data structures transforming practical performance.
Complexity classes13:14
Explore the complexity classes of running time, from polynomial (P) to nondeterministic polynomial (NP), including NP-complete and NP-hard, with reductions and polynomial-time verification.
Analysis of algorithms - loops8:01
Learn how for loops shape algorithm running time from constant to linear, quadratic, and cubic complexities, using nested loops and constant inner operations with practical examples.

Case study - O(1)4:23
Analyze constant time complexity in a one-dimensional array to fetch the first item at index zero, illustrating O(1) running time that stays independent of input size.
Case study - O(logN)10:07
Examine the logarithmic running time of binary search on a sorted list, showing how discarding half of the array each iteration leads to O(log n) worst-case performance, with implementation details.
Case study - O(N)11:24
Explore linear running time complexity through unsorted array search, examining best, average, and worst cases, and demonstrating O(n) behavior with a concrete for-loop example.
Case study - O(N*N)11:58
Analyze quadratic running time in sorting, focusing on bubble sort's adjacent comparisons and swaps; show it's slow and impractical versus insertion sort and faster sorts like merge, heap, and quicksort.
Case study - O(2^N)6:06
Analyze how computing the nth fibonacci number with recursion yields exponential running time, due to a two-child recursion tree and base cases f0 and f1.

Requirements

Internet connection

Description

This course is about algorithms running time analysis and complexity theory. In order to be able to classify algorithms we have to define limiting behaviors for functions describing the given algorithm.

We will understand running times such as O(N*logN), O(N), O(logN) and O(1) - as well as exponential and factorial running time complexities.

Thats why big O, big Ω and big θ notations came to be. We are going to talk about the theory behind complexity theory as well as we are going to see some concrete examples.

Then we will consider complexity classes including P (polynomial) as well as NP (non-deterministic polynomial), NP-complete and NP-hard complexity classes.

Section 1 - Algorithms Analysis

how to measure the running time of algorithms
running time analysis with big O (ordo), big Ω (omega) and big θ (theta) notations
complexity classes
polynomial (P) and non-deterministic polynomial (NP) algorithms

Section 2 - Algorithms Analysis (Case Studies)

constant running time O(1)
linear running time O(N)
logarithmic running time O(logN)
quadratic running time complexity O(N*N)

These concepts are fundamental if we want to have a good grasp on data structures and graph algorithms - so these topics are definitely worth considering. Hope you will like it! Thanks for joining my course, let's get started!

Who this course is for:

This course is meant for everyone who are interested in algorithms and want to get a good grasp on complexity theory

Complexity Theory - Running Time Analysis of Algorithms

What you'll learn

Explore related topics

Course content

Introduction1 lecture • 1min

Algorithms (Running Time) Analysis9 lectures • 1hr 9min

Running Time - Case Studies5 lectures • 44min

Algorhyme FREE Algorithms Visualizer App2 lectures • 2min

Course Materials (DOWNLOADS)1 lecture • 1min

Requirements

Description

Who this course is for: