Concurrent execution model in Go - Time & Space Complexity

Time Complexity: Concurrent execution model

O(1)

Understanding Time Complexity

When programs run tasks at the same time, it changes how long things take. We want to see how running tasks together affects the total work done.

How does doing many tasks at once change the time needed as we add more tasks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

import (
	"fmt"
	"sync"
	"time"
)

func worker(id int, wg *sync.WaitGroup) {
	defer wg.Done()
	time.Sleep(1 * time.Second) // simulate work
	fmt.Println("Worker", id, "done")
}

func main() {
	var wg sync.WaitGroup
	for i := 1; i <= 5; i++ {
		wg.Add(1)
		go worker(i, &wg)
	}
	wg.Wait()
}

This code runs 5 workers at the same time, each doing a 1-second task concurrently.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Starting 5 concurrent worker tasks.
• How many times: 5 times, once per worker.

How Execution Grows With Input

Each worker runs independently, so total time depends on the longest single task, not the sum.

Input Size (n)	Approx. Operations (seconds)
5	1 (all run together)
10	1 (still all run together)
100	1 (assuming enough resources to run all)

Pattern observation: Total time stays about the same as tasks increase, if they run truly in parallel.

Final Time Complexity

Time Complexity: O(1)

This means the total time does not grow with more tasks because they run at the same time.

Common Mistake

[X] Wrong: "Adding more concurrent tasks always makes the program slower because it does more work."

[OK] Correct: When tasks run at the same time, total time depends on the longest task, not the number of tasks.

Interview Connect

Understanding how concurrency affects time helps you explain real programs that do many things at once. It shows you can think about how work spreads out over time.

Self-Check

"What if each worker took different amounts of time? How would that affect the total time complexity?"

Practice

1. What is a goroutine in Go's concurrent execution model?

easy

A. A lightweight thread managed by the Go runtime

B. A type of variable used for synchronization

C. A special function that runs only once

D. A package for handling errors

Solution

1. Step 1: Understand goroutine concept

   A goroutine is a function or method that runs concurrently with other goroutines.

2. Step 2: Identify goroutine characteristics

   It is lightweight and managed by Go's runtime, unlike OS threads which are heavier.

3. Final Answer:

   A lightweight thread managed by the Go runtime -> Option A

4. Quick Check:

   Goroutine = lightweight thread [OK]

Hint: Goroutine = lightweight thread in Go [OK]

Common Mistakes:

• Confusing goroutine with OS thread
• Thinking goroutine is a variable type
• Assuming goroutine runs only once

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

easy

A. go doWork()

B. goroutine doWork()

C. start doWork()

D. run doWork()

Solution

1. Step 1: Recall goroutine syntax

   In Go, to start a goroutine, prefix the function call with the keyword go.

2. Step 2: Match syntax with options

   Only go doWork() uses the correct keyword and syntax.

3. Final Answer:

   go doWork() -> Option A

4. Quick Check:

   Start goroutine with 'go' keyword [OK]

Hint: Use 'go' before function call to start goroutine [OK]

Common Mistakes:

• Using 'goroutine' keyword instead of 'go'
• Using 'start' or 'run' which are invalid
• Omitting the 'go' keyword

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

package main
import (
  "fmt"
  "time"
)
func main() {
  go fmt.Println("Hello from goroutine")
  fmt.Println("Hello from main")
  time.Sleep(100 * time.Millisecond)
}

medium

A. No output

B. Hello from goroutine\nHello from main

C. Hello from main

D. Hello from main\nHello from goroutine

Solution

1. Step 1: Understand goroutine and main execution

   The goroutine prints "Hello from goroutine" concurrently, while main prints "Hello from main" immediately.

2. Step 2: Analyze timing with Sleep

   The time.Sleep allows the goroutine time to run before the program exits, so both lines print.

3. Final Answer:

   Hello from main\nHello from goroutine -> Option D

4. Quick Check:

   Sleep allows goroutine output after main [OK]

Hint: Sleep lets goroutine finish before program ends [OK]

Common Mistakes:

• Ignoring need for sleep to let goroutine run
• Assuming goroutine output always prints first
• Expecting no output due to race condition

4. Identify the error in this Go code snippet that tries to run a goroutine:

package main
import "fmt"
func main() {
  go func() {
    fmt.Println("Running")
  }()
}

medium

A. Missing import of time package

B. Program exits before goroutine runs

C. Syntax error in anonymous function

D. Cannot use go with anonymous functions

Solution

1. Step 1: Check syntax correctness

   The anonymous function syntax and goroutine start are correct; no syntax errors.

2. Step 2: Analyze program flow

   The main function exits immediately after starting the goroutine, so "Running" may never print.

3. Final Answer:

   Program exits before goroutine runs -> Option B

4. Quick Check:

   Program ends before goroutine runs [OK]

Hint: Add sleep or sync to wait for goroutine [OK]

Common Mistakes:

• Thinking syntax is wrong for anonymous goroutine
• Forgetting program ends immediately
• Assuming goroutine blocks main automatically

5. You want to run 3 goroutines that each print their number (1, 2, 3). Which code correctly prints all numbers reliably before the program exits?

package main
import (
  "fmt"
  "sync"
)
func main() {
  var wg sync.WaitGroup
  for i := 1; i <= 3; i++ {
    wg.Add(1)
    go func(n int) {
      defer wg.Done()
      fmt.Println(n)
    }(i)
  }
  // What should be here?
}

hard

A. wg.Done()

B. time.Sleep(1 * time.Second)

C. wg.Wait()

D. close(wg)

Solution

1. Step 1: Understand WaitGroup usage

   WaitGroup tracks goroutines; wg.Add(1) before start, wg.Done() after done.

2. Step 2: Ensure main waits for all goroutines

   Calling wg.Wait() blocks main until all goroutines call Done().

3. Final Answer:

   wg.Wait() -> Option C

4. Quick Check:

   WaitGroup.Wait() waits for goroutines [OK]

Hint: Use wg.Wait() to wait all goroutines finish [OK]

Common Mistakes:

• Using Sleep instead of WaitGroup for sync
• Trying to close WaitGroup (not allowed)
• Calling Done() in main instead of goroutine