Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities

Question

If you want examples of Algorithms/Group of Statements with Time complexity as given in the question, here is a small list -

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

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
• Counting/Bucket Sort and here too you can find a million more such examples....

---

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

---

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^2) algorithms

---

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

O(1) - most cooking procedures are O(1), that is, it takes a constant amount of time even if there are more people to cook for (to a degree, because you could run out of space in your pot/pans and need to split up the cooking)

O(logn) - finding something in your telephone book. Think binary search.

O(n) - reading a book, where n is the number of pages. It is the minimum amount of time it takes to read a book.

O(nlogn) - cant immediately think of something one might do everyday that is nlogn...unless you sort cards by doing merge or quick sort!

A simple example of O(1) might be return 23; -- whatever the input, this will return in a fixed, finite time.

A typical example of O(N log N) would be sorting an input array with a good algorithm (e.g. mergesort).

A typical example if O(log N) would be looking up a value in a sorted input array by bisection.

I can offer you some general algorithms...

• O(1): Accessing an element in an array (i.e. int i = a[9])
• O(n log n): quick or mergesort (On average)
• O(log n): Binary search

These would be the gut responses as this sounds like homework/interview kind of question. If you are looking for something more concrete it's a little harder as the public in general would have no idea of the underlying implementation (Sparing open source of course) of a popular application, nor does the concept in general apply to an "application"

O(1): finding the best next move in Chess (or Go for that matter). As the number of game states is finite it's only O(1) :-)