Comparison Based vs Non Comparison Based Sorting in DSA Go - Complexity Comparison

Time Complexity: Comparison Based vs Non Comparison Based Sorting

O(n^2) for comparison based, O(n + k) for non comparison based

Understanding Time Complexity

Sorting is a common task in programming. Different sorting methods have different speeds depending on how they work.

We want to understand how the time taken grows as the list to sort gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.

// Comparison based sorting example (Bubble Sort)
func bubbleSort(arr []int) {
  n := len(arr)
  for i := 0; i < n-1; i++ {
    for j := 0; j < n-i-1; j++ {
      if arr[j] > arr[j+1] {
        arr[j], arr[j+1] = arr[j+1], arr[j]
      }
    }
  }
}

// Non-comparison based sorting example (Counting Sort)
func countingSort(arr []int, maxVal int) []int {
  count := make([]int, maxVal+1)
  for _, val := range arr {
    count[val]++
  }
  index := 0
  for val, c := range count {
    for c > 0 {
      arr[index] = val
      index++
      c--
    }
  }
  return arr
}
    

Bubble Sort compares elements to sort, Counting Sort uses counting without direct comparisons.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

• Bubble Sort primary operation: Comparing and swapping pairs inside nested loops.
• Bubble Sort how many times: About n x n times (nested loops over array size).
• Counting Sort primary operation: Counting occurrences and then placing elements back.
• Counting Sort how many times: Counting loop runs n times, placement loop runs maxVal times.

How Execution Grows With Input

How does the work increase when the list grows?

Input Size (n)	Bubble Sort Ops (approx.)	Counting Sort Ops (approx.)
10	100 (10x10)	10 + maxVal
100	10,000 (100x100)	100 + maxVal
1000	1,000,000 (1000x1000)	1000 + maxVal

Bubble Sort grows much faster as n grows (squares), Counting Sort grows mostly with n plus the range maxVal.

Final Time Complexity

Time Complexity: O(n²) for comparison based (Bubble Sort), O(n + k) for non comparison based (Counting Sort), where k is maxVal.

Bubble Sort gets much slower as list grows; Counting Sort can be faster if maxVal is not too big.

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Some methods compare elements many times, others use counting and can be faster if conditions are right.

Interview Connect

Knowing how sorting methods differ helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

What if the range of input values (maxVal) is much larger than the number of elements? How would that affect Counting Sort's time complexity?