Algorithms and Complexity
Keep adding new skills with 10,000+ programs for $239 (usually $399). Save now.
Algorithms and Complexity
This course is part of Essential Mathematics for Computer Science Specialization
Instructor: Omar Karakchi
Included with
Ask Coursera
Recommended experience
Recommended experience
What you'll learn
Design finite automata and explain how deterministic and non-deterministic machines recognise and process formal languages.
Implement, compare, and evaluate searching and sorting algorithms, analysing their performance and correctness in different contexts.
Create recursive and iterative algorithms, identifying scenarios where each approach provides clarity, efficiency, or scalability.
Analyse algorithms with asymptotic notation, explain complexity classes like P and NP, and interpret NP-completeness in computing.
Details to know
February 2026
19 assignments
See how employees at top companies are mastering in-demand skills
Build your subject-matter expertise
- Learn new concepts from industry experts
- Gain a foundational understanding of a subject or tool
- Develop job-relevant skills with hands-on projects
- Earn a shareable career certificate
There are 4 modules in this course
Algorithms and complexity are at the heart of computer science, shaping how we design solutions and measure efficiency. This course provides a rigorous introduction to both the theory and practice of algorithms. You’ll begin with automata theory, exploring how machines recognise and process languages. You’ll then move into practical algorithmic techniques, including searching and sorting, before learning to design and evaluate recursive and iterative algorithms. Finally, you’ll study complexity theory, developing the ability to classify problems and understand computational limits. By combining abstract models with real-world techniques, this course equips you to design algorithms, assess performance, and reason about scalability. Whether you’re pursuing studies in computer science, preparing for a programming role, or aiming to strengthen your technical foundations, you’ll gain both theoretical insight and practical skills for tackling computing challenges.
In this module, we will cover the following key concepts: definitions, letters, strings, finite automata, language, deterministic and non-deterministic finite automata.
What's included
16 videos5 readings2 assignments2 ungraded labs
16 videos•Total 68 minutes
- Introduction to the course•1 minute
- Introduction•1 minute
- Basic definitions, letters, strings•4 minutes
- What is an automaton?•9 minutes
- Finite automata – example (part 1)•3 minutes
- Finite automata – example (part 2)•8 minutes
- Working with Automata Simulator•6 minutes
- Language of the automata•4 minutes
- Recognise a language•4 minutes
- Deterministic finite automata (DFA) vs nondeterministic finite automata (NFA)•4 minutes
- DFA example•4 minutes
- DFA example in Automata Simulator•4 minutes
- Computation by NFA•4 minutes
- NFA example•5 minutes
- NFA example in Automata Simulator•2 minutes
- Conclusion•4 minutes
5 readings•Total 110 minutes
- Course structure and navigation•15 minutes
- How to learn effectively on this course•15 minutes
- Course Syllabus•10 minutes
- Exercises with hints and tips•60 minutes
- Exercises with hints and tips•10 minutes
2 assignments•Total 50 minutes
- Check your understanding: End of module 1•20 minutes
- Basics•30 minutes
2 ungraded labs•Total 40 minutes
- DFA Simulator•20 minutes
- NFA Simulator•20 minutes
In this module, we will cover the following key concepts: algorithms, insertion sorts, bubble sorts, representation, binary search and heap sorts.
What's included
10 videos2 readings5 assignments1 discussion prompt1 ungraded lab
10 videos•Total 50 minutes
- What is an algorithm ?•5 minutes
- Representing algorithms•8 minutes
- Simple algorithms – insertion sort•6 minutes
- Simple algorithms – bubble sort•5 minutes
- Selection sort•5 minutes
- Search techniques•5 minutes
- Binary trees and heaps•4 minutes
- Heapify algorithm•4 minutes
- Heap sort•6 minutes
- Conclusion•2 minutes
2 readings•Total 70 minutes
- Exercises with hints and tips•10 minutes
- Binary trees and heaps•60 minutes
5 assignments•Total 107 minutes
- Check your understanding: End of module 2•20 minutes
- How else would you sort?•30 minutes
- Insertion, bubble and selection sort•25 minutes
- Binary and sequential search•12 minutes
- Heap sort•20 minutes
1 discussion prompt•Total 20 minutes
- Tell us about an algorithm that you use•20 minutes
1 ungraded lab•Total 20 minutes
- Sorting algorithms simulator: Bubble Sort and Insertion Sort•20 minutes
In this module, we will cover the following key concepts: recursion, iteration, quick sorts, merging lists, merge sorts, Shapley proofs and stable matching.
What's included
10 videos3 readings6 assignments1 discussion prompt
10 videos•Total 54 minutes
- Recursion•7 minutes
- Iterative algorithms•4 minutes
- Recursive algorithms example•5 minutes
- Quick sort•6 minutes
- Quick sort example•5 minutes
- Merging lists•5 minutes
- Merge sort•5 minutes
- The algorithm of happiness•7 minutes
- The Gale-Shapley algorithm – example and pseudocode•6 minutes
- Conclusion•3 minutes
3 readings•Total 105 minutes
- Partition and quick sort algorithms•85 minutes
- Lesson 1 exercises with hints and tips•10 minutes
- Exercises with hints and tips•10 minutes
6 assignments•Total 140 minutes
- Check your understanding: End of module 3•20 minutes
- Recursive and iterative algorithms•25 minutes
- Quick sort•20 minutes
- How does this magic work?•30 minutes
- Keep merging•30 minutes
- Stable matching•15 minutes
1 discussion prompt•Total 10 minutes
- Name an allocation problem that you know•10 minutes
In this module, we will cover the following key concepts: efficiency, bubble sorts, binary search, asymptotic complexity, Big O notation, recursion complexity, master theorem, quick sorts and merge sorts.
What's included
14 videos2 readings6 assignments1 discussion prompt
14 videos•Total 71 minutes
- Introduction•1 minute
- Efficiency – insertion sort (time complexity)•9 minutes
- Efficiency – bubble sort and binary search•7 minutes
- Asymptotic complexity•6 minutes
- Big O notation•5 minutes
- Big O notation example•5 minutes
- Using Big O to analyse selection sort•5 minutes
- Recursion complexity•11 minutes
- Master theorem•5 minutes
- Master theorem example•5 minutes
- Efficiency – quick sort•7 minutes
- Efficiency – merge sort•3 minutes
- Conclusion•1 minute
- Course summary•1 minute
2 readings•Total 20 minutes
- Module exercises with hints and tips•10 minutes
- Algorithms and Complexity: Course Summary•10 minutes
6 assignments•Total 145 minutes
- Check your understanding: End of module 4•20 minutes
- Average, worst and best case•30 minutes
- Why do we need asymptotic behaviour? [Review]•30 minutes
- Asymptotic complexity•20 minutes
- Master theorem•30 minutes
- Time complexity•15 minutes
1 discussion prompt•Total 15 minutes
- Considering approaches•15 minutes
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.
Instructor
Why people choose Coursera for their career
Frequently asked questions
To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.
More questions
Financial aid available,