Open In App

Cuckoo Hashing – Worst case O(1) Lookup!

Last Updated : 11 Jan, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Background : 

There are three basic operations that must be supported by a hash table (or a dictionary):  

  • Lookup(key): return true if key is there on the table, else false
  • Insert(key): add the item ‘key’ to the table if not already present
  • Delete(key): removes ‘key’ from the table

Collisions are very likely even if we have a big table to store keys. Using the results from the birthday paradox: with only 23 persons, the probability that two people share the same birth date is 50%! There are 3 general strategies towards resolving hash collisions: 

  • Closed addressing or Chaining: store colliding elements in an auxiliary data structure like a linked list or a binary search tree.
  • Open addressing: allow elements to overflow out of their target bucket and into other spaces.

Although above solutions provide expected lookup cost as O(1), the expected worst-case cost of a lookup in Open Addressing (with linear probing) is ?(log n) and ?(log n / log log n) in simple chaining (Source : Standford Lecture Notes). To close the gap of expected time and worst case expected time, two ideas are used: 

  • Multiple-choice hashing: Give each element multiple choices for positions where it can reside in the hash table
  • Relocation hashing: Allow elements in the hash table to move after being placed

Cuckoo Hashing : 

Cuckoo hashing applies the idea of multiple-choice and relocation together and guarantees O(1) worst case lookup time! 

  • Multiple-choice: We give a key two choices the h1(key) and h2(key) for residing.
  • Relocation: It may happen that h1(key) and h2(key) are preoccupied. This is resolved by imitating the Cuckoo bird: it pushes the other eggs or young out of the nest when it hatches. Analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location. This leaves us with the problem of re-placing the older key. 
    • If the alternate position of older key is vacant, there is no problem.
    • Otherwise, the older key displaces another key. This continues until the procedure finds a vacant position, or enters a cycle. In the case of a cycle, new hash functions are chosen and the whole data structure is ‘rehashed’. Multiple rehashes might be necessary before Cuckoo succeeds.

Insertion is expected O(1) (amortized) with high probability, even considering the possibility of rehashing, as long as the number of keys is kept below half of the capacity of the hash table, i.e., the load factor is below 50%.

Deletion is O(1) worst-case as it requires inspection of just two locations in the hash table. 
  
Illustration  

Input: 

{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}

 Hash Functions: 

h1(key) = key%11
h2(key) = (key/11)%11

ch1

Let’s start by inserting 20 at its possible position in the first table determined by h1(20):

ch2

Next: 50

ch3

Next: 53. h1(53) = 9. But 20 is already there at 9. We place 53 in table 1 & 20 in table 2 at h2(20) 

ch4

Next: 75. h1(75) = 9. But 53 is already there at 9. We place 75 in table 1 & 53 in table 2 at h2(53) 

ch6

Next: 100. h1(100) = 1. 

ch

Next: 67. h1(67) = 1. But 100 is already there at 1. We place 67 in table 1 & 100 in table 2 

ch8

Next: 105. h1(105) = 6. But 50 is already there at 6. We place 105 in table 1 & 50 in table 2 at h2(50) = 4. Now 53 has been displaced. h1(53) = 9. 75 displaced: h2(75) = 6.

ch9

Next: 3. h1(3) = 3.

ch10

Next: 36. h1(36) = 3. h2(3) = 0.

ch11

Next: 39. h1(39) = 6. h2(105) = 9. h1(100) = 1. h2(67) = 6. h1(75) = 9. h2(53) = 4. h1(50) = 6. h2(39) = 3.
Here, the new key 39 is displaced later in the recursive calls to place 105, which it displaced.

ch12

Implementation: 

Below is the implementation of Cuckoo hashing

C++




// C++ program to demonstrate working of Cuckoo
// hashing.
#include<bits/stdc++.h>
 
// upper bound on number of elements in our set
#define MAXN 11
 
// choices for position
#define ver 2
 
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
int hashtable[ver][MAXN];
 
// Array to store possible positions for a key
int pos[ver];
 
/* function to fill hash table with dummy value
 * dummy value: INT_MIN
 * number of hashtables: ver */
void initTable()
{
    for (int j=0; j<MAXN; j++)
        for (int i=0; i<ver; i++)
            hashtable[i][j] = INT_MIN;
}
 
/* return hashed value for a key
 * function: ID of hash function according to which
    key has to hashed
 * key: item to be hashed */
int hash(int function, int key)
{
    switch (function)
    {
        case 1: return key%MAXN;
        case 2: return (key/MAXN)%MAXN;
    }
}
 
/* function to place a key in one of its possible positions
 * tableID: table in which key has to be placed, also equal
   to function according to which key must be hashed
 * cnt: number of times function has already been called
   in order to place the first input key
 * n: maximum number of times function can be recursively
   called before stopping and declaring presence of cycle */
void place(int key, int tableID, int cnt, int n)
{
    /* if function has been recursively called max number
       of times, stop and declare cycle. Rehash. */
    if (cnt==n)
    {
        printf("%d unpositioned\n", key);
        printf("Cycle present. REHASH.\n");
        return;
    }
 
    /* calculate and store possible positions for the key.
     * check if key already present at any of the positions.
      If YES, return. */
    for (int i=0; i<ver; i++)
    {
        pos[i] = hash(i+1, key);
        if (hashtable[i][pos[i]] == key)
           return;
    }
 
    /* check if another key is already present at the
       position for the new key in the table
     * If YES: place the new key in its position
     * and place the older key in an alternate position
       for it in the next table */
    if (hashtable[tableID][pos[tableID]]!=INT_MIN)
    {
        int dis = hashtable[tableID][pos[tableID]];
        hashtable[tableID][pos[tableID]] = key;
        place(dis, (tableID+1)%ver, cnt+1, n);
    }
    else //else: place the new key in its position
       hashtable[tableID][pos[tableID]] = key;
}
 
/* function to print hash table contents */
void printTable()
{
    printf("Final hash tables:\n");
 
    for (int i=0; i<ver; i++, printf("\n"))
        for (int j=0; j<MAXN; j++)
            (hashtable[i][j]==INT_MIN)? printf("- "):
                     printf("%d ", hashtable[i][j]);
 
    printf("\n");
}
 
/* function for Cuckoo-hashing keys
 * keys[]: input array of keys
 * n: size of input array */
void cuckoo(int keys[], int n)
{
    // initialize hash tables to a dummy value (INT-MIN)
    // indicating empty position
    initTable();
 
    // start with placing every key at its position in
    // the first hash table according to first hash
    // function
    for (int i=0, cnt=0; i<n; i++, cnt=0)
        place(keys[i], 0, cnt, n);
 
    //print the final hash tables
    printTable();
}
 
/* driver function */
int main()
{
    /* following array doesn't have any cycles and
       hence  all keys will be inserted without any
       rehashing */
    int keys_1[] = {20, 50, 53, 75, 100, 67, 105,
                    3, 36, 39};
 
    int n = sizeof(keys_1)/sizeof(int);
 
    cuckoo(keys_1, n);
 
    /* following array has a cycle and hence we will
       have to rehash to position every key */
    int keys_2[] = {20, 50, 53, 75, 100, 67, 105,
                    3, 36, 39, 6};
 
    int m = sizeof(keys_2)/sizeof(int);
 
    cuckoo(keys_2, m);
 
    return 0;
}


Java




// Java program to demonstrate working of
// Cuckoo hashing.
import java.util.*;
 
class GFG
{
 
// upper bound on number of elements in our set
static int MAXN = 11;
 
// choices for position
static int ver = 2;
 
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
static int [][]hashtable = new int[ver][MAXN];
 
// Array to store possible positions for a key
static int []pos = new int[ver];
 
/* function to fill hash table with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
static void initTable()
{
    for (int j = 0; j < MAXN; j++)
        for (int i = 0; i < ver; i++)
            hashtable[i][j] = Integer.MIN_VALUE;
}
 
/* return hashed value for a key
* function: ID of hash function according to which
    key has to hashed
* key: item to be hashed */
static int hash(int function, int key)
{
    switch (function)
    {
        case 1: return key % MAXN;
        case 2: return (key / MAXN) % MAXN;
    }
    return Integer.MIN_VALUE;
}
 
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
  to function according to which key must be hashed
* cnt: number of times function has already been called
  in order to place the first input key
* n: maximum number of times function can be recursively
  called before stopping and declaring presence of cycle */
static void place(int key, int tableID, int cnt, int n)
{
    /* if function has been recursively called max number
    of times, stop and declare cycle. Rehash. */
    if (cnt == n)
    {
        System.out.printf("%d unpositioned\n", key);
        System.out.printf("Cycle present. REHASH.\n");
        return;
    }
 
    /* calculate and store possible positions for the key.
    * check if key already present at any of the positions.
    If YES, return. */
    for (int i = 0; i < ver; i++)
    {
        pos[i] = hash(i + 1, key);
        if (hashtable[i][pos[i]] == key)
        return;
    }
 
    /* check if another key is already present at the
       position for the new key in the table
    * If YES: place the new key in its position
    * and place the older key in an alternate position
    for it in the next table */
    if (hashtable[tableID][pos[tableID]] != Integer.MIN_VALUE)
    {
        int dis = hashtable[tableID][pos[tableID]];
        hashtable[tableID][pos[tableID]] = key;
        place(dis, (tableID + 1) % ver, cnt + 1, n);
    }
    else // else: place the new key in its position
    hashtable[tableID][pos[tableID]] = key;
}
 
/* function to print hash table contents */
static void printTable()
{
    System.out.printf("Final hash tables:\n");
 
    for (int i = 0; i < ver; i++, System.out.printf("\n"))
        for (int j = 0; j < MAXN; j++)
            if(hashtable[i][j] == Integer.MIN_VALUE)
                System.out.printf("- ");
            else
                System.out.printf("%d ", hashtable[i][j]);
 
    System.out.printf("\n");
}
 
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
static void cuckoo(int keys[], int n)
{
    // initialize hash tables to a dummy value
    // (INT-MIN) indicating empty position
    initTable();
 
    // start with placing every key at its position in
    // the first hash table according to first hash
    // function
    for (int i = 0, cnt = 0; i < n; i++, cnt = 0)
        place(keys[i], 0, cnt, n);
 
    // print the final hash tables
    printTable();
}
 
// Driver Code
public static void main(String[] args)
{
    /* following array doesn't have any cycles and
    hence all keys will be inserted without any
    rehashing */
    int keys_1[] = {20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39};
 
    int n = keys_1.length;
 
    cuckoo(keys_1, n);
 
    /* following array has a cycle and hence we will
    have to rehash to position every key */
    int keys_2[] = {20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39, 6};
 
    int m = keys_2.length;
 
    cuckoo(keys_2, m);
}
}
 
// This code is contributed by Princi Singh


Python3




# upper bound on number of elements in our set
MAXN = 11
 
# choices for position
ver = 2
 
# Auxiliary space bounded by a small multiple
# of MAXN, minimizing wastage
hashtable = [[float('inf')] * MAXN for _ in range(ver)]
 
# Array to store possible positions for a key
pos = [0] * ver
 
def init_table():
    """function to fill hash table with dummy value
    dummy value: float('inf')
    number of hashtables: ver"""
    for i in range(ver):
        for j in range(MAXN):
            hashtable[i][j] = float('inf')
 
def hash(function, key):
    """return hashed value for a key
    function: ID of hash function according to which key has to hashed
    key: item to be hashed"""
    if function == 1:
        return key % MAXN
    elif function == 2:
        return (key // MAXN) % MAXN
 
def place(key, table_id, cnt, n):
    """function to place a key in one of its possible positions
    table_id: table in which key has to be placed, also equal to function
    according to which key must be hashed
    cnt: number of times function has already been called in order to place
    the first input key
    n: maximum number of times function can be recursively called before
    stopping and declaring presence of cycle"""
    # if function has been recursively called max number of times, stop
    # and declare cycle. Rehash.
    if cnt == n:
        print(f"{key} unpositioned")
        print("Cycle present. REHASH.")
        return
 
    # calculate and store possible positions for the key. check if key
    # already present at any of the positions. If YES, return.
    for i in range(ver):
        pos[i] = hash(i + 1, key)
        if hashtable[i][pos[i]] == key:
            return
 
    # check if another key is already present at the position for the
    # new key in the table
    # If YES: place the new key in its position and place the older key
    # in an alternate position for it in the next table
    if hashtable[table_id][pos[table_id]] != float('inf'):
        dis = hashtable[table_id][pos[table_id]]
        hashtable[table_id][pos[table_id]] = key
        place(dis, (table_id + 1) % ver, cnt + 1, n)
    else: # else: place the new key in its position
        hashtable[table_id][pos[table_id]] = key
 
def print_table():
    """function to print hash table contents"""
    print("Final hash tables:")
    for i in range(ver):
        print()
        for j in range(MAXN):
            if hashtable[i][j] == float('inf'):
                print("- ", end="")
            else:
                print(f"{hashtable[i][j]} ", end="")
    print()
 
def cuckoo(keys, n):
    # initialize hash tables to a dummy value (float('inf'))
    # indicating empty position
    init_table()
 
    # start with placing every key at its position in the first
    # hash table according to first hash function
    for i in range(n):
        cnt = 0
        place(keys[i], 0, cnt, n)
 
    # print the final hash tables
    print_table()
 
# driver function
def main():
    # following array doesn't have any cycles and
    # hence  all keys will be inserted without any
    # rehashing
    keys_1 = [20, 50, 53, 75, 100, 67, 105, 3, 36, 39]
 
    cuckoo(keys_1, len(keys_1))
 
    # following array has a cycle and hence we will
    # have to rehash to position every key
    keys_2 = [20, 50, 53, 75, 100, 67, 105, 3, 36, 39, 6]
 
    cuckoo(keys_2, len(keys_2))
 
if __name__ == "__main__":
    main()
 
# This code is contributed by vikramshirsath177


C#




// C# program to demonstrate working of
// Cuckoo hashing.
using System;
     
class GFG
{
 
// upper bound on number of
// elements in our set
static int MAXN = 11;
 
// choices for position
static int ver = 2;
 
// Auxiliary space bounded by a small
// multiple of MAXN, minimizing wastage
static int [,]hashtable = new int[ver, MAXN];
 
// Array to store
// possible positions for a key
static int []pos = new int[ver];
 
/* function to fill hash table
with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
static void initTable()
{
    for (int j = 0; j < MAXN; j++)
        for (int i = 0; i < ver; i++)
            hashtable[i, j] = int.MinValue;
}
 
/* return hashed value for a key
* function: ID of hash function
according to which key has to hashed
* key: item to be hashed */
static int hash(int function, int key)
{
    switch (function)
    {
        case 1: return key % MAXN;
        case 2: return (key / MAXN) % MAXN;
    }
    return int.MinValue;
}
 
/* function to place a key in one of
its possible positions
* tableID: table in which key
has to be placed, also equal to function
according to which key must be hashed
* cnt: number of times function has already
been called in order to place the first input key
* n: maximum number of times function
can be recursively called before stopping and
declaring presence of cycle */
static void place(int key, int tableID,
                  int cnt, int n)
{
    /* if function has been recursively
    called max number of times,
    stop and declare cycle. Rehash. */
    if (cnt == n)
    {
        Console.Write("{0} unpositioned\n", key);
        Console.Write("Cycle present. REHASH.\n");
        return;
    }
 
    /* calculate and store possible positions
    * for the key. Check if key already present
    at any of the positions. If YES, return. */
    for (int i = 0; i < ver; i++)
    {
        pos[i] = hash(i + 1, key);
        if (hashtable[i, pos[i]] == key)
        return;
    }
 
    /* check if another key is already present
    at the position for the new key in the table
    * If YES: place the new key in its position
    * and place the older key in an alternate position
    for it in the next table */
    if (hashtable[tableID,
              pos[tableID]] != int.MinValue)
    {
        int dis = hashtable[tableID, pos[tableID]];
        hashtable[tableID, pos[tableID]] = key;
        place(dis, (tableID + 1) % ver, cnt + 1, n);
    }
    else // else: place the new key in its position
    hashtable[tableID, pos[tableID]] = key;
}
 
/* function to print hash table contents */
static void printTable()
{
    Console.Write("Final hash tables:\n");
 
    for (int i = 0; i < ver;
             i++, Console.Write("\n"))
        for (int j = 0; j < MAXN; j++)
            if(hashtable[i, j] == int.MinValue)
                Console.Write("- ");
            else
                Console.Write("{0} ",
                        hashtable[i, j]);
 
    Console.Write("\n");
}
 
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
static void cuckoo(int []keys, int n)
{
    // initialize hash tables to a
    // dummy value (INT-MIN)
    // indicating empty position
    initTable();
 
    // start with placing every key
    // at its position in the first
    // hash table according to first
    // hash function
    for (int i = 0, cnt = 0;
             i < n; i++, cnt = 0)
        place(keys[i], 0, cnt, n);
 
    // print the final hash tables
    printTable();
}
 
// Driver Code
public static void Main(String[] args)
{
    /* following array doesn't have
    any cycles and hence all keys
    will be inserted without any rehashing */
    int []keys_1 = {20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39};
 
    int n = keys_1.Length;
 
    cuckoo(keys_1, n);
 
    /* following array has a cycle and
    hence we will have to rehash to
    position every key */
    int []keys_2 = {20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39, 6};
 
    int m = keys_2.Length;
 
    cuckoo(keys_2, m);
}
}
 
// This code is contributed by PrinciRaj1992


Javascript




<script>
 
// Javascript program to demonstrate working of
// Cuckoo hashing.
 
// upper bound on number of elements in our set
let MAXN = 11;
   
// choices for position
let ver = 2;
   
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
let hashtable = new Array(ver);
for (var i = 0; i < hashtable.length; i++) {
    hashtable[i] = new Array(2);
}
   
// Array to store possible positions for a key
let pos = Array(ver).fill(0);
   
/* function to fill hash table with dummy value
* dummy value: let_MIN
* number of hashtables: ver */
function initTable()
{
    for (let j = 0; j < MAXN; j++)
        for (let i = 0; i < ver; i++)
            hashtable[i][j] = Number.MIN_VALUE;
}
   
/* return hashed value for a key
* function: ID of hash function according to which
    key has to hashed
* key: item to be hashed */
function hash(function, key)
{
    switch (function)
    {
        case 1: return key % MAXN;
        case 2: return (Math.floor(key / MAXN)) % MAXN;
    }
    return Number.MIN_VALUE;
}
   
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
  to function according to which key must be hashed
* cnt: number of times function has already been called
  in order to place the first input key
* n: maximum number of times function can be recursively
  called before stopping and declaring presence of cycle */
function place(key, tableID, cnt, n)
{
    /* if function has been recursively called max number
    of times, stop and declare cycle. Rehash. */
    if (cnt == n)
    {
        document.write(key + " unpositioned" + "<br/>");
        document.write("Cycle present. REHASH." + "<br/>");
        return;
    }
   
    /* calculate and store possible positions for the key.
    * check if key already present at any of the positions.
    If YES, return. */
    for (let i = 0; i < ver; i++)
    {
        pos[i] = hash(i + 1, key);
        if (hashtable[i][pos[i]] == key)
            return;
    }
   
    /* check if another key is already present at the
       position for the new key in the table
    * If YES: place the new key in its position
    * and place the older key in an alternate position
    for it in the next table */
    if (hashtable[tableID][pos[tableID]] != Number.MIN_VALUE)
    {
        let dis = hashtable[tableID][pos[tableID]];
        hashtable[tableID][pos[tableID]] = key;
        place(dis, (tableID + 1) % ver, cnt + 1, n);
    }
    else // else: place the new key in its position
        hashtable[tableID][pos[tableID]] = key;
}
   
/* function to print hash table contents */
function printTable()
{
    document.write("Final hash tables:" + "<br/>");
   
    for (let i = 0; i < ver; i++, document.write("<br/>"))
        for (let j = 0; j < MAXN; j++)
            if(hashtable[i][j] == Number.MIN_VALUE)
                document.write("- ");
            else
                document.write(hashtable[i][j] + " ");
   
    document.write("<br/>");
}
   
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
function cuckoo(keys, n)
{
    // initialize hash tables to a dummy value
    // (let-MIN) indicating empty position
    initTable();
   
    // start with placing every key at its position in
    // the first hash table according to first hash
    // function
    for (let i = 0, cnt = 0; i < n; i++, cnt = 0)
        place(keys[i], 0, cnt, n);
   
    // print the final hash tables
    printTable();
}
 
// Driver program
 
      /* following array doesn't have any cycles and
    hence all keys will be inserted without any
    rehashing */
    let keys_1 = [20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39];
   
    let n = keys_1.length;
   
    cuckoo(keys_1, n);
   
    /* following array has a cycle and hence we will
    have to rehash to position every key */
    let keys_2 = [20, 50, 53, 75, 100,
                    67, 105, 3, 36, 39, 6];
   
    let m = keys_2.length;
   
    cuckoo(keys_2, m);
       
</script>


Output

Final hash tables:
- 100 - 36 - - 50 - - 75 - 
3 20 - 39 53 - 67 - - 105 - 

105 unpositioned
Cycle present. REHASH.
Final hash tables:
- 67 - 3 - - 39 - - 53 - 
6 20 - 36 50 - 75 - - 100 - 

Time Complexity: O(N), the time complexity of the Cuckoo Hashing algorithm is O(N), where N is the number of keys to be stored in the hash table. This is because the algorithm requires only one pass over the list of keys to place them in the hash table.

Auxiliary Space: O(N), the space complexity of the Cuckoo Hashing algorithm is O(N), where N is the number of keys stored in the hash table. This is because the algorithm requires an auxiliary space of size equal to the hash table, where all the keys are stored.

Generalizations of cuckoo hashing that use more than 2 alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed. Example: if we use 3 hash functions, it’s safe to load 91% and still be operating within expected bounds.



Previous Article
Next Article

Similar Reads

Cuckoo Hashing in Python
Cuckoo Hashing derived its name from the cuckoo bird, which lays its eggs in the nests of other birds, replacing their eggs with its own. Cuckoo Hashing works in a similar manner which involves moving the values to different location whenever there is a collision in the hash table. In this article, we will learn how to implement Cuckoo Hashing in P
5 min read
When does the worst case of Quicksort occur?
The answer depends on the strategy for choosing pivot. In early versions of Quick Sort where the leftmost (or rightmost) element is chosen as a pivot, the worst occurs in the following cases. 1) Array is already sorted in the same order. 2) Array is already sorted in reverse order. 3) All elements are the same (a special case of cases 1 and 2) Sinc
4 min read
K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time
We recommend reading the following posts as a prerequisite for this post.K’th Smallest/Largest Element in Unsorted Array K’th Smallest/Largest Element in Unsorted Array | Expected Linear TimeGiven an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all
15+ min read
Can QuickSort be implemented in O(nLogn) worst case time complexity?
The worst-case time complexity of a typical implementation of QuickSort is O(n2). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when the input array is sorted or reverses sorted and either the first or last element is picked as a pivot. Although randomized QuickSort works well even when
15+ min read
QuickSort Tail Call Optimization (Reducing worst case space to Log n )
Prerequisite : Tail Call Elimination In QuickSort, partition function is in-place, but we need extra space for recursive function calls. A simple implementation of QuickSort makes two calls to itself and in worst case requires O(n) space on function call stack. The worst case happens when the selected pivot always divides the array such that one pa
12 min read
Find a permutation that causes worst case of Merge Sort
Given a set of elements, find which permutation of these elements would result in worst case of Merge Sort.Asymptotically, merge sort always takes O(n Log n) time, but the cases that require more comparisons generally take more time in practice. We basically need to find a permutation of input elements that would lead to maximum number of compariso
12 min read
Worst, Average and Best Case Analysis of Algorithms
In the previous post, we discussed how Asymptotic analysis overcomes the problems of the naive way of analyzing algorithms. But let's take an overview of the asymptotic notation and learn about What is Worst, Average, and Best cases of an algorithm: Popular Notations in Complexity Analysis of Algorithms1. Big-O NotationWe define an algorithm’s wors
14 min read
Reverse bits using lookup table in O(1) time
Given an unsigned integer, reverse all bits of it and return the number with reversed bits. Examples: Input : n = 1 Output : 2147483648 On a machine with size of unsigned bit as 32. Reverse of 0....001 is 100....0. Input : n = 2147483648 Output : 1 In the previous post we had seen two method that solved this problem in O(n) &amp; O(logn ) time. Her
7 min read
Count set bits in an integer using Lookup Table
Write an efficient program to count number of 1s in binary representation of an integer.Examples: Input : n = 6Output : 2Binary representation of 6 is 110 and has 2 set bits Input : n = 13Output : 3Binary representation of 11 is 1101 and has 3 set bits In the previous post we had seen different method that solved this problem in O(log n) time. In t
6 min read
Count trailing zero bits using lookup table
Given an integer, count the number of trailing zeroes. For example, for n = 12, its binary representation is 1100 and number of trailing zero bits is 2. Examples : Input : 8 Output : 3 Binary of 8 is 1000, so there are three trailing zero bits. Input : 18 Output : 1 Binary of 18 is 10010, so there is one trailing zero bit. A simple solution is to t
7 min read
Article Tags :
Practice Tags :