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

What are some algorithms which we use daily that has O(1), O(n log n) and O(log n) complexities?

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"