My Blog: 2015

Tuesday, August 18, 2015

TIME CONSUMED(WASTED) IN HUMAN SLEEP, BE AWARE..!!

Found this interesting article on net,

If someone stay alive for 70 years and sleeps daily for

1) 6 hours: spends 17.5 years of his life in Sleep state.
2) 8 hours: spends 23.3 years of his life in Sleep state.
3) 9 hours: spends 26.31 years of his life in Sleep state.
4) 10 hours: spends 29.1 years of his life in Sleep state.

Next time someone complaining not sleeping give this figures, now we have all reason to wake up late..!!!

Sunday, August 16, 2015

Big O - CheetSheet.

Legend

Excellent Good Fair Bad Horrible

Data Structure Operations

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Stack	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Singly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Doubly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Skip List	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
Hash Table	`-`	`O(1)`	`O(1)`	`O(1)`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Binary Search Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Cartesian Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B-Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Red-Black Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Splay Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
AVL Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`O(n)`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Shell Sort	`O(n)`	`O((nlog(n))^2)`	`O((nlog(n))^2)`	`O(1)`
Bucket Sort	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`

Graph Operations

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|V\| + \|E\|)`	`O(\|E\|)`	`O(\|V\|)`
Incidence list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|E\|)`	`O(\|E\|)`	`O(\|E\|)`
Adjacency matrix	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(1)`	`O(\|V\|^2)`	`O(1)`	`O(1)`
Incidence matrix	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|E\|)`

Heap Operations

Type	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	`-`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(m+n)`
Linked List (unsorted)	`-`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(1)`	`O(1)`
Binary Heap	`O(n)`	`O(1)`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(m+n)`
Binomial Heap	`-`	`O(1)`	`O(log(n))`	`O(log(n))`	`O(1)`	`O(log(n))`	`O(log(n))`
Fibonacci Heap	`-`	`O(1)`	`O(log(n))`	`O(1)`	`O(1)`	`O(log(n))`	`O(1)`

Big-O Complexity Chart

Big O Complexity Graph

Note: Content courtesy by Eric

Subscribe to: Posts (Atom)