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

Question

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

Answer 1

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.

Answer 2

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"

Answer 3

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.

Answer 4

Making coffee for yourself every morning is O(1). Reading newspaper is probably O(logn) in terms of time vs interest

Answer 5

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

Answer 6

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

Answer 7

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!

Answer 8

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

Answer 9

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)
{
    .
    .
    .
}