Back To Module Home

Data Structures & Algorithms In Go

0% completed

Time Complexity

Introduction and Asymptotic Analysis

Big-O, Omega and Theta Notations

Complexity Analysis of Algorithms

Time Complexity Order

Deriving an Algorithm's Runtime Function

Examples Related to Time Complexities

Master Theorem Examples

Arrays

Challenge: Sum Array Solution Review: Sum Array Challenge: Sequential Search Solution Review: Sequential Search Challenge: Binary Search Solution Review: Binary Search Challenge: Finding the Largest Sum Subarray Solution Review: Finding the Largest Sum Subarray Challenge: Rotating an Array by k Positions Solution Review: Rotating an Array by k Positions Challenge: Array Waveform Solution Review: Array Waveform Challenge: Index Array Solution Review: Index Array Challenge: Sorting From 1 to n Solution Review: Sorting From 1 to n Challenge: Smallest Positive Missing Number Solution Review: Smallest Positive Missing Number Challenge: Maximum, Minimum Array Solution Review: Maximum, Minimum Array Challenge: Array Index Maximum Difference Solution Review: Array Index Maximum Difference Quiz: Arrays

Recursive Functions

Recursive Functions Challenge: Factorial Solution Review: Factorial Challenge: Print Base 16 Integers Solution Review: Print Base 16 Integers Challenge: Greatest Common Divisor Solution Review: Greatest Common Divisor Challenge: Fibonacci Numbers Solution Review: Fibonacci Numbers Challenge: All Permutations of an Integer List Solution Review: All Permutations of an Integer List Challenge: Tower of Hanoi Solution Review: Tower of Hanoi Quiz: Recursion

Approaches to Solve Algorithm Design Problems

Introduction and Constraints Idea Generation Complexities, Coding, and Testing Example and Summary

Data Structures in Go

Abstract Data Type Go Collection Framework Stack Queue Tree Priority Queue / Heap Hash-Table Dictionary Set and Counter Symbol Table Graph

Sorting

Introduction Sorting Algorithm Bubble Sort Modified Bubble Sort Insertion Sort Selection Sort Merge Sort Quick Sort Quick Select Count Sort External Sort (External Merge-Sort)Stable Sort Choosing the Best Sorting Algorithm Challenge: Partitioning of 0s and 1s Solution Review: Partitioning of 0s and 1s Challenge: Partitioning of 0s, 1s, and 2s Solution Review: Partitioning of 0s, 1s and 2s

Stack

Introduction to Stack The Stack Abstract Data Type Challenge: Stack Using Array Solution Review: Stack Using Array Challenge: Stack Using Linked List Solution Review: Stack Using Linked List System Stack and Method Calls Challenge: Sorted Insert Solution Review: Sorted Insert Challenge: Sort Stack Solution Review: Sort Stack Challenge: Bottom Insert Solution Review: Bottom Insert Challenge: Reverse Stack Solution Review: Reverse Stack Challenge: Reverse k Elements in a Stack Solution Review: Reverse k Element in a Stack Challenge: Balanced Parentheses Solution Review: Balanced Parenthesis Challenge: Min Stack Solution Review: Min Stack Challenge: Max Depth Parenthesis Solution Review: Max Depth Parenthesis Challenge: Longest Continuous Balanced Parenthesis Solution Review: Longest Continuous Balanced Parenthesis Challenge: Reverse Parenthesis Solution Review: Reverse Parentheses Challenge: Find Duplicate Parentheses Solution Review: Find Duplicate Parenthesis Challenge: Print Parenthesis Number Solution Review: Print Parentheses Number Infix, Prefix, and Postfix Expressions Challenge: Infix-to-Postfix Conversion Solution Review: Infix-to-Postfix Conversion Challenge: Infix-to-Prefix Conversion Solution Review: Infix-to-Prefix Conversion

Queue

Introduction to Queue Queue Implementation Using an Array Queue Implementation Using a LinkedList Queue Implementation Using Circular Linked List Queue Implementation Using Doubly Linked List Challenge: Queue Using Stack Solution Review: Queue Using Stack Challenge: Reverse Queue Solution Review: Reverse Queue Challenge: Reverse k Elements in a Queue Solution Review: Reverse k Elements in a Queue

Tree

Introduction to Tree Types of Trees Introduction to Binary Trees Challenge: Create a Complete Binary Tree Solution Review: Create a Complete Binary Tree Challenge: Print Pre-Order Traversal Solution Review: Print Pre-Order Traversal Challenge: Print Post-order Traversal Solution Review: Print Post-order Traversal Challenge: Print In-order Traversal Solution Review: Print In-Order Traversal Challenge: Print level-order Traversal Solution Review: Print Level-order Traversal Challenge: Print Depth First Without Recursion Solution Review: Print Depth First Without Using the Recursion Challenge: Print Level Order Line by Line Using Two Queues Solution Review: Print Level Order Line by Line Using Two Queues Challenge: Print a Tree in Level-order Line by Line Using a Queue Solution Review: Print Level Order Line by Line Using One Queue Challenge: Print Spiral Tree Solution Review: Print Spiral Tree Challenge: nth Pre-order Solution Review: nth Pre-Order Challenge: nth Post-order Solution Review: nth Post-Order Challenge: nth In-Order Solution Review: nth In-Order Challenge: Print All the Paths Solution Review: Print All the Paths Challenge: Number of Elements Solution Review: Number of Elements Challenge: Sum of All Nodes in a Binary Tree Solution Review: Sum of All Nodes in a Binary Tree Challenge: Find Number of Leaf Nodes Solution Review: Find Number of Leaf Nodes Challenge: Number of Full Nodes in a Binary Tree Solution Review: Number of Full Nodes in a Binary Tree Challenge: Search Value in a Binary Tree Solution Review: Search Value in a Binary Tree Challenge: Find Max in Binary Tree Solution Review: Find Max in Binary Tree Challenge: Tree Depth Solution Review: Tree Depth Challenge: Identical Trees Solution Review: Identical Trees Challenge: Copy Tree Solution Review: Copy Tree Challenge: Copy Mirror Tree Solution Review: Copy Mirror Tree Challenge: Free Tree Solution Review: Free Tree Challenge: Check Completeness of Tree Using Queue Solution Review: Check Completeness of Tree Using Queue Challenge: Check Completeness of Tree Using Recursion Solution Review: Check Completeness of Tree using Recursion Challenge: Is Tree a Heap?Solution Review: Is Tree a Heap Challenge: Tree to List Conversion using Recursion Solution Review: Tree to List Conversion using Recursion

Binary Search Tree

Introduction to a Binary Search Tree (BST)Challenge: Create a Binary Search Tree From the Sorted List Solution Review: Create a Binary Search Tree From the Sorted List Challenge: Insertion Solution Review: Insertion Challenge: Find Node Solution Review: Find Node Challenge: Find Min Solution Review: Find Min Challenge: Find Max Solution Review: Find Max Challenge: Is It a BST?Solution Review: Is It a BST?Challenge: Delete Node Solution Review: Delete Node Challenge: Least Common Ancestor Solution Review: Least Common Ancestor Challenge: Print Tree Nodes within a Range Solution Review: Print Tree Nodes within a Range Challenge: Trim the Tree Nodes Outside Range Solution Review: Trim the Tree Nodes Outside Range Challenge: Find Ceil and Floor Values in a BST Solution Review: Find Ceil and Floor Values in a BST Challenge: Is It a BST Array?Solution Review: Is It a BST Array?

Conclusion

...

/

Examples Related to Time Complexities

Examples Related to Time Complexities

Let's dive deeper into the time complexity analysis by looking into some examples in this lesson.

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)$ .

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(n^c)$ , its time complexity is $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 $i$ times, and the outer loop iterates $n$ 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)+\cdots)$ = $O(n(n+1)/2)$ ...