Common concurrency patterns in Go - Time & Space Complexity

Time Complexity: Common concurrency patterns

O(n)

Understanding Time Complexity

When using concurrency in Go, it's important to understand how the program's work grows as more tasks run at the same time.

We want to see how the time to finish changes when we add more concurrent parts.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

import (
	"fmt"
	"sync"
)

func worker(id int, wg *sync.WaitGroup) {
	defer wg.Done()
	// simulate work
}

func main() {
	var wg sync.WaitGroup
	n := 5
	wg.Add(n)
	for i := 0; i < n; i++ {
		go worker(i, &wg)
	}
	wg.Wait()
	fmt.Println("All workers done")
}

This code runs several workers at the same time using goroutines and waits for all to finish.

Identify Repeating Operations

• Primary operation: Starting and running n goroutines concurrently.
• How many times: The loop runs n times to launch workers.

How Execution Grows With Input

As we increase the number of workers, the program launches more goroutines, but they run at the same time.

Input Size (n)	Approx. Operations
10	10 goroutines started, run concurrently
100	100 goroutines started, run concurrently
1000	1000 goroutines started, run concurrently

Pattern observation: The number of goroutines grows linearly with input, but total time depends on how they run together.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the number of concurrent tasks started.

Common Mistake

[X] Wrong: "Running many goroutines always makes the program faster and time stays the same."

[OK] Correct: Even if goroutines run at the same time, starting many can add overhead and the actual speed depends on CPU and synchronization.

Interview Connect

Understanding how concurrency affects time helps you explain how programs handle many tasks and manage resources efficiently.

Self-Check

"What if we added a channel to limit how many goroutines run at once? How would the time complexity change?"

Practice

1. What is the primary purpose of a WaitGroup in Go concurrency?

easy

A. To limit the number of goroutines running at the same time

B. To send data safely between goroutines

C. To wait for a collection of goroutines to finish before continuing

D. To create new goroutines

Solution

1. Step 1: Understand WaitGroup's role

   A WaitGroup is used to wait for multiple goroutines to complete their work.

2. Step 2: Compare with other concurrency tools

   Channels send data, semaphores limit concurrency, and goroutines run functions concurrently.

3. Final Answer:

   To wait for a collection of goroutines to finish before continuing -> Option C

4. Quick Check:

   WaitGroup = wait for goroutines [OK]

Hint: WaitGroup waits for goroutines to finish, not for data passing [OK]

Common Mistakes:

• Confusing WaitGroup with channels
• Thinking WaitGroup limits goroutines
• Using WaitGroup to send data

2. Which of the following is the correct syntax to start a new goroutine calling function doWork()?

easy

A. run doWork()

B. goroutine doWork()

C. start doWork()

D. go doWork()

Solution

1. Step 1: Recall goroutine syntax

   In Go, the keyword go before a function call starts it as a goroutine.

2. Step 2: Check options

   Only go doWork() matches the correct syntax; others are invalid keywords.

3. Final Answer:

   go doWork() -> Option D

4. Quick Check:

   Start goroutine with 'go' keyword [OK]

Hint: Start goroutine with 'go' keyword before function call [OK]

Common Mistakes:

• Using non-existent keywords like 'goroutine' or 'start'
• Omitting 'go' keyword
• Trying to run goroutine without parentheses

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

package main
import (
  "fmt"
  "sync"
)
func main() {
  var wg sync.WaitGroup
  wg.Add(2)
  go func() {
    fmt.Println("Hello from goroutine 1")
    wg.Done()
  }()
  go func() {
    fmt.Println("Hello from goroutine 2")
    wg.Done()
  }()
  wg.Wait()
  fmt.Println("All goroutines finished")
}

medium

A. Hello from goroutine 2
Hello from goroutine 1

B. Hello from goroutine 1
Hello from goroutine 2
All goroutines finished

C. Hello from goroutine 1
All goroutines finished
Hello from goroutine 2

D. All goroutines finished
Hello from goroutine 1
Hello from goroutine 2

Solution

1. Step 1: Understand WaitGroup usage

   The program adds 2 to the WaitGroup, then starts 2 goroutines that each print a message and call wg.Done().

2. Step 2: Analyze output order

   The main goroutine waits for both goroutines to finish before printing "All goroutines finished". The two goroutine prints can appear in any order but both appear before the final print.

3. Final Answer:

   Hello from goroutine 1 Hello from goroutine 2 All goroutines finished -> Option B

4. Quick Check:

   WaitGroup ensures final print after goroutines [OK]

Hint: WaitGroup.Wait blocks until all Done calls complete [OK]

Common Mistakes:

• Assuming main prints before goroutines
• Ignoring WaitGroup synchronization
• Expecting goroutine prints after final print

4. Identify the error in this Go code snippet using channels:

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

medium

A. Second read from channel blocks forever

B. Channel is not closed before reading

C. Channel should be buffered to send data

D. Goroutine is not started correctly

Solution

1. Step 1: Analyze channel sends and receives

   The goroutine sends one value (10) into the channel. The main goroutine reads twice from the channel.

2. Step 2: Identify blocking behavior

   The first read gets 10 successfully. The second read waits for another value that never comes, causing a deadlock (blocks forever).

3. Final Answer:

   Second read from channel blocks forever -> Option A

4. Quick Check:

   One send, two receives causes blocking [OK]

Hint: Reads must match sends; extra read blocks forever [OK]

Common Mistakes:

• Thinking channel must be closed before reading
• Assuming buffered channel fixes blocking here
• Believing goroutine not started properly

5. You want to create a worker pool in Go to process 5 jobs concurrently but limit to 2 workers at a time. Which pattern correctly implements this?

hard

A. Use a buffered channel of size 2 as a semaphore to limit goroutines, and a WaitGroup to wait for all jobs

B. Start 5 goroutines without limit and use a WaitGroup to wait

C. Use an unbuffered channel to send jobs and no WaitGroup

D. Use a mutex to lock and unlock workers

Solution

1. Step 1: Understand worker pool concurrency limit

   To limit concurrent workers, a buffered channel (semaphore) of size 2 can control how many goroutines run simultaneously.

2. Step 2: Use WaitGroup to wait for all jobs

   A WaitGroup tracks all 5 jobs to ensure main waits until all finish before exiting.

3. Final Answer:

   Use a buffered channel of size 2 as a semaphore to limit goroutines, and a WaitGroup to wait for all jobs -> Option A

4. Quick Check:

   Semaphore + WaitGroup = controlled concurrency [OK]

Hint: Semaphore channel limits workers; WaitGroup waits for all [OK]

Common Mistakes:

• Starting all goroutines without limit
• Not using WaitGroup to wait for completion
• Using mutex incorrectly for concurrency limit