Search⌘ K
Home
Courses
Data Structures & Algorithms In Go

Examples Related to Time Complexities

Explore detailed examples of time complexity to understand how different code structures like loops and nested loops impact algorithm efficiency. Learn to analyze complexities such as linear, quadratic, logarithmic, and more, to improve your skills in optimizing Go programs.

We'll cover the following...

Let’s better understand the time complexity by going through a few examples.

Example 1: for loop

The case below is a for loop. We have a time complexity of O(n)O(n).

Go (1.6.2)
package main
import(
  "fmt"
)
func fun1(n int) int {
  m := 0
  for i := 0; i < n; i++ {
    m += 1
  }
 return m
}
func main() {
  fmt.Println("N = 100, Number of instructions O(n) ::", fun1(100))
}

The statement on line 10 takes constant time. Hence, it doesn’t affect the time complexity of the loop.

Example 2: Nested for loop

In this case, we have a nested loop where the total number of loops is 2. Both loops run n times. According to formula O(nc)O(n^c), its time complexity is O(n2​​​)O(n^2​​​).

Go (1.6.2)
package main
import(
  "fmt"
)
func fun2(n int) int {
 m := 0
 for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        m += 1
    }
  }
 return m
}
func main() {
  fmt.Println("N = 100, Number of instructions O(n^2) ::", fun2(100))
}

Example 3: Arithmetic series

This example shows that the inner loop iterates ii times, and the outer loop iterates nn times.

The exact number of steps will go the same way as those of the arithmetic series. In this case, the time complexity will be: O(n+(n−1)+(n−2)+⋯ )O(n+(n-1)+(n-2)+\cdots) = O(n(n+1)/2)O(n(n+1)/2) ...