Big O notation: Python to Rust

This course is part of Rust for Data Engineering Specialization

Instructor: Noah Gift

Included with

Learn more

5 modules

Gain insight into a topic and learn the fundamentals.

Intermediate level

Some related experience required

6 hours to complete

Flexible schedule

Learn at your own pace

5 modules

Gain insight into a topic and learn the fundamentals.

Intermediate level

Some related experience required

6 hours to complete

Flexible schedule

Learn at your own pace

Details to know

Shareable certificate

Add to your LinkedIn profile

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the Rust for Data Engineering Specialization

When you enroll in this course, you'll also be enrolled in this Specialization.

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 5 modules in this course

Big O notation: Python to Rust is a hands-on algorithmic complexity course for engineers transitioning from Python to Rust who want to reason rigorously about how their code scales. You will learn Big O, Big Theta, and Big Omega notation; analyze the time and space complexity of common operations on Python and Rust data structures (list/Vec, dict/HashMap, set/HashSet, tuple, slice, BTreeMap); and compare measured performance in both languages on identical workloads. The course covers amortized analysis, recursion and master theorem, worst case versus expected case, the cost of allocation and borrowing, and how Rust's ownership model affects real-world constants even when asymptotic complexity is identical. You will profile Python code with cProfile and timeit, profile Rust code with criterion and perf, and translate Python algorithms (search, sort, hashing, graph traversal, dynamic programming) into idiomatic Rust while keeping or improving complexity guarantees. By the end of the course, you will be able to predict performance, choose appropriate data structures, justify rewrites from Python to Rust on quantitative grounds, and communicate trade-offs to a team. Part of the Rust for Data Engineering specialization.

Set the foundation: define what "complexity" actually means as a claim, and meet the three modes of proof — analytical, empirical, and structural — you'll use to defend complexity claims throughout the course. Learn to recognize falsifiable vs. unfalsifiable performance claims and build the worked-example habit you'll need in later modules.

What's included

3 videos7 readings

3 videosTotal 4 minutes

1.1.1 What Complexity Means And Three Modes1 minute
1.2.1 Reading A Complexity Claim1 minute
1.3.1 Depyler Transpiler Shortcut1 minute

7 readingsTotal 70 minutes

About This Course10 minutes
Key Terms: What "Complexity" Means + Three Modes of Proof10 minutes
Reflection: What "Complexity" Means + Three Modes of Proof10 minutes
Key Terms: Reading a Complexity Claim — Falsifiability10 minutes
Reflection: Reading a Complexity Claim — Falsifiability10 minutes
Key Terms: Depyler — the Transpiler Shortcut10 minutes
Reflection: Depyler — the Transpiler Shortcut10 minutes

Empirical proof in practice: measure runtime with reproducible benchmarks. Three head-to-head Python→Rust translations — list comprehension to iterator, dict lookup to HashMap, and sorted() to sort_unstable — let you read benchmark output, control for noise, and decide when measured speedups are real and when they're artifacts.

What's included

3 videos6 readings

3 videosTotal 4 minutes

2.1.1 List Comp To Iterator1 minute
2.2.1 Dict Lookup To Hashmap1 minute
2.3.1 Sorted To Sort Unstable1 minute

6 readingsTotal 60 minutes

Key Terms: List Comprehension → Iterator10 minutes
Reflection: List Comprehension → Iterator10 minutes
Key Terms: x in dict → HashMap Lookup10 minutes
Reflection: x in dict → HashMap Lookup10 minutes
Key Terms: sorted() → sort_unstable10 minutes
Reflection: sorted() → sort_unstable10 minutes

Structural proof in practice: use the type system to make incorrect programs impossible to compile. Translating Optional[T] to Option<T>, try/except to Result<T,E>, and ad-hoc state machines to Rust enums turns runtime errors into compile-time errors — a structural guarantee no benchmark can refute.

What's included

3 videos6 readings

3 videosTotal 3 minutes

3.1.1 Optional To Option1 minute
3.2.1 Try Except To Result1 minute
3.3.1 Mutable Default To Ownership1 minute

6 readingsTotal 60 minutes

Key Terms: Optional[T] → Option<T>10 minutes
Reflection: Optional[T] → Option<T>10 minutes
Key Terms: try/except → Result<T, E>10 minutes
Reflection: try/except → Result<T, E>10 minutes
Key Terms: Mutable Default Arg → Ownership10 minutes
Reflection: Mutable Default Arg → Ownership10 minutes

Translation with runtime consequences: each translation in this module replaces a Python construct (generators, subprocess calls, parallel loops) with a Rust equivalent that carries different runtime guarantees — memory profile, error surface, parallelism model — not just "the same thing, but faster."

What's included

3 videos6 readings

3 videosTotal 3 minutes

4.1.1 Generator To Iterator1 minute
4.2.1 Subprocess To Command1 minute
4.3.1 Threading To Rayon1 minute

6 readingsTotal 60 minutes

Key Terms: Generator → Iterator10 minutes
Reflection: Generator → Iterator10 minutes
Key Terms: Subprocess → Command10 minutes
Reflection: Subprocess → Command10 minutes
Key Terms: Threading → Rayon10 minutes
Reflection: Threading → Rayon10 minutes

Capstone: bring all three modes of proof together on a real translation. Two case studies — a three-mode playbook end to end, and a deliberate "when NOT to translate" example — train your judgment about when a Python→Rust port pays off and when it would just add cost without measurable benefit.

What's included

2 videos5 readings1 assignment

2 videosTotal 2 minutes

5.1.1 Three-Mode Playbook End To End1 minute
5.2.1 When NOT to Translate1 minute

5 readingsTotal 50 minutes

Key Terms: Three-Mode Playbook End to End10 minutes
Reflection: Three-Mode Playbook End to End10 minutes
Key Terms: When NOT to Translate10 minutes
Reflection: When NOT to Translate10 minutes
Before You Go: Share Your Feedback10 minutes

1 assignmentTotal 30 minutes

Final Quiz: The Three-Mode Proof Playbook30 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

Noah Gift

Pragmatic AI Labs

58 Courses3,782 learners

Offered by

Pragmatic AI Labs

Explore more from Software Development

Pragmatic AI Labs
Claude From Zero
Course
Pragmatic AI Labs
HelixDB From Zero
Course
Pragmatic AI Labs
Shipping Rust
Course
Pragmatic AI Labs
Graph Algorithms with Rust
Course

Why people choose Coursera for their career

Felipe M.

Learner since 2018

"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."

Jennifer J.

Learner since 2020

"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."

Larry W.

Learner since 2021

"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."

Chaitanya A.

"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Unlock access to 10,000+ courses with a subscription
Advance your career with an online degree
Earn a degree from world-class universities - 100% online
Join over 4,700 global companies that choose Coursera for Business

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.