compute.info

- Θ notation -

f(n) = Θ(g(n))

There exist positive constants c1, c2, and n0 such that          

0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.

We say g(n) is an asymptotically tight bound for f(n) if f(n) = Θ(g(n)). Informally we can say, as far as time complexity or order of growth, these functions are equal.

- O notation -

f(n) = O(g(n)) There exist positive constants c and n0 such that

0 ≤ f(n) ≤ cg(n) for all n ≥ n0.

We say g(n) is an asymptotic upper bound for f(n) if f(n) = O(g(n)).

- Ω notation -

f(n) = Ω(g(n)) There exist positive constants c and n0 such that           

0 ≤ cg(n) ≤ f(n) for all n ≥ n0.

We say g(n) is an asymptotic lower bound for f(n) if f(n) = Ω(g(n)).

- o notation -

f(n) = o(g(n)) For any positive constant c > 0, there exists a constant           

n0 > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n0.

We say f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)). We can also express this as the following limit

limn→∞(f(n)/g(n)) = 0

- ω notation -

f(n) = ω(g(n)) For any positive constant c > 0, there exists a constant           

n0 > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n0.

We say f(n) is asymptotically bigger than g(n) if f(n) = ω(g(n)). We can also express this as the following limit.

limn→∞(f(n)/g(n)) = ∞

- Properties -

Transitivity:

  f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))   f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))   f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))   f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))   f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))

Reflexivity:

  f(n) = Θ(f(n))   f(n) = O(f(n))   f(n) = Ω(f(n))

Symmetry:

   f(n) = Θ(g(n)) iff g(n) = Θ(f(n))

Transpose symmetry:

  f(n) = O(g(n)) iff g(n) = Ω(f(n))   f(n) = o(g(n)) iff g(n) = ω(f(n))

- Informal Comparison -

  f(n) = O(g(n)) ≈ a ≤ b   f(n) = Ω(g(n)) ≈ a ≥ b   f(n) = Θ(g(n)) ≈ a = b   f(n) = o(g(n)) ≈ a < b   f(n) = ω(g(n)) ≈ a > b

- Note -

tcplistener.ps1:

Extract hostname of the machine being debugged either in live KD or from a kernel dump.

Make a folder with the following name to access all available settings on Windows 8.x.

Powershell one-liners to see if a remote port is open. The target port is open if the command returns with no errors.

Given a binary tree, convert it to an array and vice versa.

int *BinaryTreeToArray(Node *root) {     int *arr = new int[8];     // Skipping index 0 for simplicity     BinaryTreeToArrayHelper(root, arr, 8, 1);     return arr; } void BinaryTreeToArrayHelper(Node *n, int *arr, int size, int index) {     if (!n || index > size - 1)         return;     arr[index] = n->value;     BinaryTreeToArrayHelper(n->left, arr, size, index * 2);     BinaryTreeToArrayHelper(n->right, arr, size, index * 2 + 1); }