Three-way handshake in Computer Networks - Time & Space Complexity

Time Complexity: Three-way handshake

O(n)

Understanding Time Complexity

When devices start a connection using the three-way handshake, it is important to understand how the steps grow as more connections happen.

We want to know how the time to complete the handshake changes when many devices try to connect.

Scenario Under Consideration

Analyze the time complexity of the following handshake process.

// Simplified three-way handshake steps
send SYN to server
wait for SYN-ACK from server
send ACK to server
connection established
    

This code shows the three main message exchanges to start a connection between two devices.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending and receiving three messages in sequence.
• How many times: Exactly three message exchanges per connection.

How Execution Grows With Input

Each connection requires three messages. If we have more connections, the total messages grow proportionally.

Input Size (number of connections)	Approx. Messages Sent
10	30
100	300
1000	3000

Pattern observation: The total messages increase directly with the number of connections.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete handshakes grows linearly as more connections start.

Common Mistake

[X] Wrong: "The handshake time grows faster than the number of connections because of waiting times stacking up."

[OK] Correct: Each handshake happens independently and requires a fixed number of steps, so total time grows directly with connections, not faster.

Interview Connect

Understanding how connection setup time scales helps you explain network performance clearly and confidently in real-world discussions.

Self-Check

What if the handshake required an extra message for security checks? How would the time complexity change?

Practice

1. What is the main purpose of the three-way handshake in computer networks?

easy

A. To disconnect a network session

B. To encrypt data before sending

C. To establish a reliable connection between two computers

D. To assign IP addresses automatically

Solution

1. Step 1: Understand the role of the three-way handshake

   The three-way handshake is a process used in TCP to start a connection reliably.

2. Step 2: Identify the correct purpose

   It ensures both computers agree to communicate before data transfer begins.

3. Final Answer:

   To establish a reliable connection between two computers -> Option C

4. Quick Check:

   Three-way handshake = establish connection [OK]

Hint: Remember: handshake means starting a connection [OK]

Common Mistakes:

• Confusing handshake with encryption
• Thinking it disconnects sessions
• Mixing it up with IP address assignment

2. Which sequence correctly represents the messages exchanged during the TCP three-way handshake?

easy

A. SYN, SYN-ACK, ACK

B. ACK, SYN, SYN-ACK

C. SYN-ACK, ACK, SYN

D. ACK, ACK, SYN

Solution

1. Step 1: Recall the message order in TCP handshake

   The client first sends SYN to request connection.

2. Step 2: Identify the correct sequence

   The server replies with SYN-ACK, then client sends ACK to confirm.

3. Final Answer:

   SYN, SYN-ACK, ACK -> Option A

4. Quick Check:

   Order is SYN -> SYN-ACK -> ACK [OK]

Hint: Think: Client SYN, Server SYN-ACK, Client ACK [OK]

Common Mistakes:

• Mixing up the order of messages
• Forgetting the SYN-ACK step
• Assuming ACK comes first

3. If a client sends a SYN message but does not receive a SYN-ACK response, what will happen next?

medium

A. The client immediately sends an ACK message

B. The client will resend the SYN message after a timeout

C. The connection is established without confirmation

D. The client closes the connection instantly

Solution

1. Step 1: Understand client behavior on no response

   If the client does not get SYN-ACK, it assumes the message was lost or server is unreachable.

2. Step 2: Identify the retry mechanism

   The client waits for a timeout, then resends the SYN to try again.

3. Final Answer:

   The client will resend the SYN message after a timeout -> Option B

4. Quick Check:

   No SYN-ACK -> resend SYN [OK]

Hint: No reply? Client retries SYN after waiting [OK]

Common Mistakes:

• Assuming connection established without SYN-ACK
• Thinking client sends ACK first
• Believing client closes connection immediately

4. A network engineer notices that after sending SYN, the client never receives SYN-ACK. Which of these is the most likely cause?

medium

A. The server is not listening on the target port

B. The client sent an ACK instead of SYN

C. The client skipped sending SYN-ACK

D. The client closed the connection too early

Solution

1. Step 1: Analyze the missing SYN-ACK response

   If no SYN-ACK arrives, the server likely did not respond to SYN.

2. Step 2: Identify common reasons for no response

   One common reason is the server not listening on the requested port, so it ignores SYN.

3. Final Answer:

   The server is not listening on the target port -> Option A

4. Quick Check:

   No SYN-ACK means server not listening [OK]

Hint: No SYN-ACK? Check if server port is open [OK]

Common Mistakes:

• Blaming client for sending wrong message
• Thinking client sends SYN-ACK
• Assuming client closed connection early

5. During the three-way handshake, what could happen if the final ACK message is lost in transit?

hard

A. The server assumes connection is established without ACK

B. The client will resend SYN immediately

C. The connection will close automatically

D. The server will retransmit SYN-ACK until it receives ACK

Solution

1. Step 1: Understand the role of the final ACK

   The final ACK confirms the client received the server's SYN-ACK and completes the handshake.

2. Step 2: Identify server behavior if ACK is lost

   If the server does not get ACK, it will retransmit SYN-ACK to prompt the client again.

3. Final Answer:

   The server will retransmit SYN-ACK until it receives ACK -> Option D

4. Quick Check:

   Lost ACK -> server retries SYN-ACK [OK]

Hint: Lost ACK? Server keeps sending SYN-ACK [OK]

Common Mistakes:

• Thinking client resends SYN instead
• Assuming connection closes automatically
• Believing server accepts connection without ACK