Notes on Big-O from different sources

Runtimes of Common Big-O Functions

Here is a table of common Big-O functions:

</tr> </thead>

</tr>

</tr>

</tr>

</tr>

</tr>

</tr>

</tr> </tbody> </table>

Big-O
Name
1
Constant
log(n)
Logarithmic
n
Linear
nlog(n)
Log Linear
n^2
Quadratic
n^3
Cubic
2^n
Exponential

Table of Big-O for common list operations

Operation

Big-O Efficiency </tr> </thead>

index []

O(1) </tr>

index assignment

O(1) </tr>

append

O(1) </tr>

pop()

O(1) </tr>

pop(i)

O(n) </tr>

insert(i,item)

O(n) </tr>

del operator

O(n) </tr>

iteration

O(n) </tr>

contains (in)

O(n) </tr>

get slice [x:y]

O(k) </tr>

del slice

O(n) </tr>

set slice

O(n+k) </tr>

reverse

O(n) </tr>

concatenate

O(k) </tr>

sort

O(n log n) </tr>

multiply

O(nk) </tr> </tbody> </table>

Dictionaries/hash tables

Dictionaires in Python are a form of 'hash table', with O(1) for getting and setting items.

Big-O efficiencies of common dictionary operations:

Operation	Big-O Efficiency
copy	O(n)
get item	O(1)
set item	O(1)
delete item	O(1)
contains (in)	O(1)
iteration	O(n)

General Big-O Complexities for common operations and data structures

---

Fastest sorting algorithms:

• $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances;
• Quicksort, which is worst-case $O(n^2)$ but quite often $O(nlogn)$ with good constants and properties and which can be used as a general-purpose sorting procedure;
• $O(nlogn)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms
• $O(n)O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.