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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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   -

User · Answer

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

User · Answer

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

User · Answer

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  lt   1  return number  return Fibonacci number - 2    Fibonacci number - 1

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

Examples related to algorithm

Examples related to time-complexity