traceroute for path tracing in Linux CLI - Time & Space Complexity

Time Complexity: traceroute for path tracing

O(n)

Understanding Time Complexity

When using traceroute, we want to know how long it takes to find the path to a destination.

We ask: How does the time grow as the number of network hops increases?

Scenario Under Consideration

Analyze the time complexity of the following traceroute command.

traceroute example.com

# traceroute sends packets with increasing TTL values
# to discover each hop on the path to example.com

This command finds the route packets take by sending probes with increasing hop limits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending probe packets with increasing TTL values.
• How many times: Once per hop until the destination is reached or max hops exceeded.

How Execution Grows With Input

Each hop adds one more probe packet to send and wait for a reply.

Input Size (hops)	Approx. Operations (probes sent)
10	10
20	20
30	30

Pattern observation: The number of operations grows directly with the number of hops.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete traceroute grows linearly with the number of hops on the path.

Common Mistake

[X] Wrong: "Traceroute time depends only on the destination, not the number of hops."

[OK] Correct: Each hop requires a separate probe, so more hops mean more steps and more time.

Interview Connect

Understanding how traceroute scales helps you reason about network delays and troubleshooting steps in real systems.

Self-Check

"What if traceroute sent multiple probes per hop instead of one? How would the time complexity change?"