Apa itu Big O Notation

Big O Notation adalah notasi matematis yang mendeskripsikan perilaku pembatas suatu fungsi ketika argumennya cenderung ke arah nilai tertentu atau tak terhingga.

Sederhananya, notasi O Besar mendeskripsikan kompleksitas kode Anda menggunakan istilah aljabar.

5 Jenis Big O Notation dan contohnya

1.O(1) time

• Accessing Array Index (int a = ARR[5];)
• Inserting a node in Linked List
• Pushing and Poping on Stack
• Insertion and Removal from Queue
• Finding out the parent or left/right child of a node in a tree stored in Array
• Jumping to Next/Previous element in Doubly Linked List

2.O(n) time

In a nutshell, all Brute Force Algorithms, or Noob ones which require linearity, are based on O(n) time complexity

• Traversing an array
• Traversing a linked list
• Linear Search
• Deletion of a specific element in a Linked List (Not sorted)
• Comparing two strings
• Checking for Palindrome

3.O(log n) time

• Binary Search
• Finding largest/smallest number in a binary search tree
• Certain Divide and Conquer Algorithms based on Linear functionality
• Calculating Fibonacci Numbers — Best Method The basic premise here is NOT using the complete data, and reducing the problem size with every iteration

4.O(n log n) time

The factor of ‘log n’ is introduced by bringing into consideration Divide and Conquer. Some of these algorithms are the best optimized ones and used frequently.

• Merge Sort
• Heap Sort
• Quick Sort
• Certain Divide and Conquer Algorithms based on optimizing O(n²) algorithm

O(n^2) time

These ones are supposed to be the less efficient algorithms if their O(nlogn) counterparts are present. The general application may be Brute Force here.

• Bubble Sort
• Insertion Sort
• Selection Sort
• Traversing a simple 2D array