Bird
Raised Fist0
Linux CLIscripting~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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)
1010
2020
3030

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?"

Practice

(1/5)
1. What is the main purpose of the traceroute command in Linux?
easy
A. To display current network connections
B. To list all files in a directory
C. To change the IP address of the system
D. To show the path data takes to reach a destination

Solution

  1. Step 1: Understand traceroute function

    The traceroute command traces the route packets take to reach a network host.

  2. Step 2: Compare options

    Options A, B, and D describe unrelated commands or functions.

  3. Final Answer:

    To show the path data takes to reach a destination -> Option D

  4. Quick Check:

    Traceroute purpose = show path [OK]
Hint: Traceroute maps network path hops quickly [OK]
Common Mistakes:
  • Confusing traceroute with ping
  • Thinking traceroute changes network settings
  • Mixing traceroute with file commands
2. Which of the following is the correct syntax to run traceroute to example.com with a maximum of 5 hops?
easy
A. traceroute -m 5 example.com
B. traceroute -max 5 example.com
C. traceroute --maxhops=5 example.com
D. traceroute -h 5 example.com

Solution

  1. Step 1: Recall traceroute max hops option

    The option -m sets the max number of hops in traceroute.

  2. Step 2: Check syntax correctness

    Only traceroute -m 5 example.com uses the correct option and format.

  3. Final Answer:

    traceroute -m 5 example.com -> Option A

  4. Quick Check:

    Max hops option = -m [OK]
Hint: Use -m to limit hops in traceroute [OK]
Common Mistakes:
  • Using -max or --maxhops which are invalid
  • Confusing -h (help) with hop limit
  • Placing options after the hostname
3. What will be the output of the command traceroute -n 8.8.8.8?
medium
A. It shows an error because -n is invalid
B. It shows the route to 8.8.8.8 with hostnames only, no IP addresses
C. It shows the route to 8.8.8.8 with IP addresses only, no hostnames
D. It shows the route with both hostnames and IP addresses

Solution

  1. Step 1: Understand the -n option in traceroute

    The -n option disables hostname resolution and shows IP addresses only.

  2. Step 2: Analyze output format

    Therefore, the output will list IP addresses without hostnames.

  3. Final Answer:

    It shows the route to 8.8.8.8 with IP addresses only, no hostnames -> Option C

  4. Quick Check:

    -n means no hostname lookup [OK]
Hint: -n shows IPs only, no names [OK]
Common Mistakes:
  • Thinking -n shows hostnames
  • Assuming -n causes error
  • Expecting both IP and hostname with -n
4. You run traceroute -m 3 example.com but it shows more than 3 hops. What is the likely cause?
medium
A. The -m option was ignored because of a syntax error
B. Traceroute always shows all hops regardless of -m
C. The command is correct; traceroute shows up to 3 hops only
D. The hostname resolves to multiple IPs causing extra hops

Solution

  1. Step 1: Check syntax of the command

    The correct syntax requires a space between -m and the number, so -m 3 is correct.

  2. Step 2: Consider possible syntax errors

    If the option was typed incorrectly (like -m3 without space), traceroute may ignore it and show default hops.

  3. Step 3: Evaluate other options

    Traceroute does not always ignore -m; it respects it if syntax is correct. Multiple IPs do not increase hops count.

  4. Final Answer:

    The -m option was ignored because of a syntax error -> Option A

  5. Quick Check:

    Syntax error causes option ignore [OK]
Hint: Check option syntax carefully for -m [OK]
Common Mistakes:
  • Using -m3 without space causing ignore
  • Assuming traceroute ignores -m always
  • Confusing hops with IP resolution count
5. You want to trace the path to example.com but skip hostname lookups and limit hops to 4. Which command achieves this?
hard
A. traceroute -m 4 -h example.com
B. traceroute -n -m 4 example.com
C. traceroute --no-hostname --max-hops=4 example.com
D. traceroute -4 -n example.com

Solution

  1. Step 1: Identify options for skipping hostname and limiting hops

    -n skips hostname lookup; -m 4 limits hops to 4.

  2. Step 2: Verify option correctness and order

    traceroute -n -m 4 example.com uses both correctly. traceroute -m 4 -h example.com uses invalid -h. traceroute --no-hostname --max-hops=4 example.com uses non-standard options. traceroute -4 -n example.com limits to IPv4 but not hops.

  3. Final Answer:

    traceroute -n -m 4 example.com -> Option B

  4. Quick Check:

    -n and -m 4 combined = correct command [OK]
Hint: Combine -n and -m for no hostname and hop limit [OK]
Common Mistakes:
  • Using -h instead of -m for hops
  • Assuming --no-hostname is valid
  • Confusing -4 (IPv4) with hop limit
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard