Channel synchronization in Go - Time & Space Complexity

Time Complexity: Channel synchronization

O(n)

Understanding Time Complexity

When using channels in Go, it's important to know how the program's speed changes as more data passes through. We want to see how waiting for communication affects the time it takes.

How does the program's running time grow when more messages are sent and received through channels?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func main() {
  ch := make(chan int)

  go func() {
    for i := 0; i < 1000; i++ {
      ch <- i
    }
    close(ch)
  }()

  for val := range ch {
    _ = val
  }
}

This code sends 1000 integers through a channel from one goroutine to the main goroutine, which receives them one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending and receiving each integer through the channel.
• How many times: Exactly 1000 times, once per integer.

How Execution Grows With Input

Each message sent must be received, so the total work grows directly with the number of messages.

Input Size (n)	Approx. Operations
10	About 10 sends and 10 receives
100	About 100 sends and 100 receives
1000	About 1000 sends and 1000 receives

Pattern observation: The total steps increase evenly as the number of messages grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to send and receive messages grows in a straight line with the number of messages.

Common Mistake

[X] Wrong: "Channels add a fixed delay, so time stays the same no matter how many messages are sent."

[OK] Correct: Each message requires a send and receive step, so more messages mean more total time.

Interview Connect

Understanding how channel communication scales helps you write efficient concurrent programs and explain your reasoning clearly in interviews.

Self-Check

"What if we used a buffered channel with capacity 1000 instead of an unbuffered channel? How would the time complexity change?"

Practice

1. What happens when a goroutine tries to send data on an unbuffered channel if no other goroutine is ready to receive?

easy

A. The sending goroutine waits until another goroutine receives the data.

B. The data is lost and the program continues immediately.

C. The program crashes with a runtime error.

D. The data is buffered automatically for later use.

Solution

1. Step 1: Understand unbuffered channel behavior

   Unbuffered channels require both sender and receiver to be ready at the same time for communication.

2. Step 2: Analyze sending on unbuffered channel

   If no goroutine is ready to receive, the sending goroutine blocks and waits until a receiver is ready.

3. Final Answer:

   The sending goroutine waits until another goroutine receives the data. -> Option A

4. Quick Check:

   Unbuffered channel send blocks until receive [OK]

Hint: Unbuffered sends block until a receiver is ready [OK]

Common Mistakes:

• Thinking data is buffered automatically
• Assuming send never blocks
• Believing program crashes on send

2. Which of the following is the correct syntax to create a buffered channel of integers with capacity 3 in Go?

easy

A. ch := chan int{3}

B. ch := make(chan int)

C. ch := make(chan int, 3)

D. ch := new(chan int, 3)

Solution

1. Step 1: Recall channel creation syntax

   Channels are created using make with type and optional buffer size: make(chan Type, capacity).

2. Step 2: Identify correct buffered channel syntax

   To create a buffered channel of int with capacity 3, use make(chan int, 3).

3. Final Answer:

   ch := make(chan int, 3) -> Option C

4. Quick Check:

   Buffered channel syntax = make(chan Type, capacity) [OK]

Hint: Use make(chan Type, capacity) for buffered channels [OK]

Common Mistakes:

• Omitting buffer size for buffered channel
• Using new() instead of make()
• Incorrect channel literal syntax

3. What will be the output of the following Go program?

package main
import "fmt"
func main() {
  ch := make(chan string)
  go func() {
    ch <- "hello"
  }()
  msg := <-ch
  fmt.Println(msg)
}

medium

A. Compilation error

B. No output

C. Deadlock runtime error

D. hello

Solution

1. Step 1: Analyze channel and goroutine

   A goroutine sends "hello" on an unbuffered channel ch, while main receives from ch.

2. Step 2: Understand synchronization

   The send and receive synchronize, so main receives "hello" and prints it.

3. Final Answer:

   hello -> Option D

4. Quick Check:

   Send and receive synchronize, printing message [OK]

Hint: Unbuffered channel send/receive synchronize to pass data [OK]

Common Mistakes:

• Expecting deadlock because of goroutine
• Thinking channel is buffered by default
• Assuming no output due to concurrency

4. Identify the error in this Go code snippet involving channel synchronization:

package main
func main() {
  ch := make(chan int)
  ch <- 5
  val := <-ch
  println(val)
}

medium

A. No error, code runs fine.

B. Sending on channel blocks forever causing deadlock.

C. Channel is not initialized properly.

D. Receiving from channel blocks forever causing deadlock.

Solution

1. Step 1: Check channel creation and usage

   Channel ch is unbuffered and created correctly with make(chan int).

2. Step 2: Analyze send operation

   Sending on unbuffered channel blocks until another goroutine receives. Here, send happens before receive, no other goroutine receives, so it blocks forever.

3. Final Answer:

   Sending on channel blocks forever causing deadlock. -> Option B

4. Quick Check:

   Send blocks without concurrent receiver [OK]

Hint: Send on unbuffered channel blocks if no receiver ready [OK]

Common Mistakes:

• Thinking receive blocks first
• Assuming channel is nil
• Believing code runs without deadlock

5. You want to run three tasks concurrently and wait for all to finish before exiting. Which Go code snippet correctly uses channels to synchronize all tasks?

hard

A. Use a buffered channel with capacity 3; each goroutine sends a signal when done; main receives 3 signals.

B. Use an unbuffered channel; main sends signals to goroutines to start; no synchronization on finish.

C. Use a buffered channel with capacity 1; goroutines send signals; main receives once.

D. Use no channels; just start goroutines and exit main immediately.

Solution

1. Step 1: Understand synchronization goal

   Main must wait for all 3 goroutines to finish before exiting.

2. Step 2: Analyze channel usage options

   Buffered channel with capacity 3 allows all goroutines to send done signals without blocking; main receives 3 signals to know all finished.

3. Final Answer:

   Use a buffered channel with capacity 3; each goroutine sends a signal when done; main receives 3 signals. -> Option A

4. Quick Check:

   Buffered channel capacity = number of goroutines to sync [OK]

Hint: Use buffered channel sized to goroutines for sync signals [OK]

Common Mistakes:

• Using unbuffered channel causing deadlock
• Receiving fewer signals than goroutines
• Not waiting for goroutines at all