What is the time complexity of indexing, inserting and removing from common data structures?

Information on this topic is now available on Wikipedia at: Search data structure +———————-+———-+————+———-+————–+ | | Insert | Delete | Search | Space Usage | +———————-+———-+————+———-+————–+ | Unsorted array | O(1) | O(1) | O(n) | O(n) | | Value-indexed array | O(1) | O(1) | O(1) | O(n) | | Sorted array | O(n) …

Read more

Difference between O(logn) and O(nlogn)

Think of it as O(n*log(n)), i.e. “doing log(n) work n times”. For example, searching for an element in a sorted list of length n is O(log(n)). Searching for the element in n different sorted lists, each of length n is O(n*log(n)). Remember that O(n) is defined relative to some real quantity n. This might be …

Read more

Example of Big O of 2^n

Algorithms with running time O(2^N) are often recursive algorithms that solve a problem of size N by recursively solving two smaller problems of size N-1. This program, for instance prints out all the moves necessary to solve the famous “Towers of Hanoi” problem for N disks in pseudo-code void solve_hanoi(int N, string from_peg, string to_peg, …

Read more