Layer caching and ordering in Docker - Time & Space Complexity

Time Complexity: Layer caching and ordering

O(n)

Understanding Time Complexity

When building Docker images, the order of commands affects how long builds take. We want to understand how build time grows as we add more layers.

How does changing the order of steps impact the time to rebuild an image?

Scenario Under Consideration

Analyze the time complexity of this Dockerfile snippet.

FROM python:3.12-slim
COPY requirements.txt /app/
RUN pip install -r /app/requirements.txt
COPY src/ /app/src/
RUN python /app/src/setup.py

This Dockerfile installs dependencies first, then copies source code and runs setup.

Identify Repeating Operations

Look for repeated work when rebuilding the image.

• Primary operation: Running pip install and copying files.
• How many times: Each build may rerun pip install if requirements change, or copy source files if they change.

How Execution Grows With Input

As the number of dependencies or source files grows, build time changes.

Input Size (n)	Approx. Operations
10 dependencies	Fast install, quick copy
100 dependencies	Longer install, same copy time
1000 dependencies	Much longer install, same copy time

Changing source files triggers copying and setup steps, which grow with source size. Installing dependencies grows with number of packages.

Final Time Complexity

Time Complexity: O(n)

This means build time grows roughly in direct proportion to the number of dependencies or source files changed.

Common Mistake

[X] Wrong: "Changing source files always triggers reinstalling dependencies."

[OK] Correct: Docker caches layers, so if dependency files don't change, install step is skipped, saving time.

Interview Connect

Understanding layer caching helps you write efficient Dockerfiles and speeds up builds, a useful skill in real projects and interviews.

Self-Check

What if we moved the COPY src/ /app/src/ step before installing dependencies? How would the time complexity change?