157

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

3
  • 6
    Why wiki? It's neither a poll nor subjective. She wants specific examples of the big-O properties.
    – paxdiablo
    Commented Oct 20, 2009 at 5:46
  • 4
    Wiki because it has no single correct answer, it has multiple answers.
    – Jason S
    Commented Oct 20, 2009 at 13:22
  • 2
    Wikipedia has a good list, too. en.wikipedia.org/wiki/Time_complexity
    – Homer6
    Commented Jun 26, 2014 at 17:38

12 Answers 12

342

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(n!) time

  • Solving the travelling salesman problem via brute-force search
  • generating all unrestricted permutations of a partially ordered set;
  • finding the determinant with Laplace expansion
  • enumerating all partitions of a set
8
  • 6
    What about n!? I've been wondering what common algorithm uses n!?
    – Y_Y
    Commented Jan 30, 2014 at 22:00
  • Accessing a HashMap value as well as more complex algorithms like an LRU implementation which achieve O(1) using a HashMap and a doubly-linked-list or implementing a stack with PUSH/POP/MIN functionality. Also the recursive implementation of Fibonacci fall under N!.
    – ruralcoder
    Commented Mar 23, 2014 at 4:26
  • 37
    My OCD wants you to switch the O(log n) list to be before the O(n) list so that the list is in order from best to worst. haha :)
    – Sam Eaton
    Commented Sep 12, 2015 at 4:54
  • 7
    Traversing a 2D array is actually O(n x m) unless it's a square matrix.
    – Simon Peck
    Commented Sep 30, 2015 at 23:53
  • 4
    The 'traveling salesman' problem is an example of n! (n factorial) as well
    – Ju66ernaut
    Commented Dec 15, 2017 at 18:46
40

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!

4
  • 2
    It takes a lot longer to cook a roast than a mini-roast :-)
    – paxdiablo
    Commented Oct 20, 2009 at 6:00
  • 7
    but usually it takes the same time to cook two mini-roast vs one mini-roast, provided your oven is large enough to fit it in!
    – Chii
    Commented Oct 20, 2009 at 7:27
  • 1
    Very insightful! I suppose the task of compiling a telephone or address book from a list of names/numbers might be O(n log n) Commented Jan 3, 2014 at 20:43
  • An example of O(n log n) that you might do in everyday life: Translating a text by looking up every word in a dictionary.
    – amarillion
    Commented Feb 26 at 10:36
32

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.

11

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"

0
5

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) :-)

2
  • 5
    Yes, you can usually trade off time for space. I've actually done this for a tic-tac-toe game since there are only 3^9 states (less if you handle rotations intelligently). Chess, however, has a somewhat larger number of states :-)
    – paxdiablo
    Commented Oct 20, 2009 at 5:58
  • 1
    The problem is that I will live only O(1) nanoseconds, and you surely know which O(1) will occur first...
    – zardav
    Commented Jul 19, 2019 at 12:21
4

O(1) - Deleting an element from a doubly linked list. e.g.

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}
3

The complexity of software application is not measured and is not written in big-O notation. It is only useful to measure algorithm complexity and to compare algorithms in the same domain. Most likely, when we say O(n), we mean that it's "O(n) comparisons" or "O(n) arithmetic operations". That means, you can't compare any pair of algorithms or applications.

3
  • 2
    That's not really true. If an algorithm has O(N) time complexity, that means that its runtime is bounded by k * N steps for some constant k. It is not really important whether "steps" are CPU cycles, assembly instructions, or (simple) C operations. That details is hidden by the constant k. Commented Oct 20, 2009 at 5:44
  • Not to mention that in many practical cases the "c" of an O(logN) algorithm makes it worse than a simpler O(N) algorithm.
    – Zed
    Commented Oct 20, 2009 at 5:47
  • Haha, yes, and by N we then mean the length of input on a Turing machine tape--which makes vertical form of division take exponential time to implement. :-) Each domain has its own requirements and its own precinct of abstracting.
    – P Shved
    Commented Oct 20, 2009 at 5:54
3

You can add following algorithms to your list:

O(1) - Determining if a number is even or odd; Working with HashMap

O(logN) - computing x^N,

O(N Log N) - Longest increasing subsequence

1

O (n log n) is famously the upper bound on how fast you can sort an arbitrary set (assuming a standard and not highly parallel computing model).

1

O(2N)

O(2N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2N) function is the recursive calculation of Fibonacci numbers:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
1
  • Tower of Hanoi would have been a better example. Commented Aug 23, 2019 at 8:44
0

0(logn)-Binary search, peak element in an array(there can be more than one peak) 0(1)-in python calculating the length of a list or a string. The len() function takes 0(1) time. Accessing an element in an array takes 0(1) time. Push operation in a stack takes 0(1) time. 0(nlogn)-Merge sort. sorting in python takes nlogn time. so when you use listname.sort() it takes nlogn time.

Note-Searching in a hash table sometimes takes more than constant time because of collisions.

0

O(1)

DoSomething();

O(n)

for(i=0; i<n; i++){
    DoSomething();
} 

O(log n)

for(i=0; i<n; i=i*2){
    DoSomething();
} 

O(n log n)

for(i=0; i<n; i++){
   for(j=0; j<n; j=j*2){
      DoSomething();
   } 
} 

O(log^2 n)

for(i=0; i<n; i=i*2){
    for(j=0; j<n; j=j*2){
        DoSomething();
    } 
}

O(n^2)

for(i=0; i<n; i=i++){
    for(j=0; j<n; j=j++){
        DoSomething();
    } 
}

O(2^n)

int DoSomething(int n)
{
    if (n<1) 
       return n;
    return DoSomething(n-1);
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.