Last updated Unknown

Status: Tags: #archivedCards/cmpt125/bigo Links: Big O Notation

Big O Notation Orders of Magnitude

O(1) – bounded by some absolute constant (e.g.,  <= 100)​

• 1+2+3+…+n = ;; n*(n+1)/2

• 0+1+2+…+n-1 ;; n*(n-1)/2

• Checking if statements in Big O;;O(1)

O(log N) – logarithmic complexity – very fast​

• Binary Search

O(N) ?

• linear, constant times the size of the input
• For loops

O(N log N) – Almost as good as linear.​ O(N2) – quadratic time​ O(N3), O(N4), …O(N7)… O(Nconst) – polynomial ​ O(2N) – exponential: considered as very inefficient​ O(4N) – exponential: even worse than 2N​ O(N!) – more than exponential

Comparisons to Big O’s

f(N) = $1.5N^2$ + 4N + 3 ?

Backlinks

1

list from Big O Notation Orders of Magnitude AND !outgoing(Big O Notation Orders of Magnitude)

References:

Created:: 2021-10-18 21:23