Big O Notation in 1 minute

See also:

2 minutes explanation

5 minutes explanation

8 minutes explanation

Big O Notation is a mathematical function used in computer science to describe how complex an algorithm is.

There are two kinds of complexities: time and space.

Typically, there are three tiers (known as asymptotic notations) to solve for:

Best case → Big Omega or Ω(n)
Average case → Big Theta or Θ(n)
Worst case → Big O or O(n)

O(1) – Constant time complexity

One single step.

OPs
|
|
|
|
|
| .  .  .  .  .  .  .
|
+----------------------------- Elements

O(log n) – Logarithmic time complexity

If it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100.

OPs
|
|                                     . 
|                    . 
|           . 
|      . 
|   .
| .
+----------------------------- Elements

O(n) – Linear time complexity

Loop of n steps.

OPs
|                   .
|                . 
|             . 
|          . 
|       . 
|    .
| .
+----------------------------- Elements

O(n²) – Quadratic time complexity

Loop inside a loop.

OPs
|                  .
|                 . 
|               .  
|            . 
|         . 
|     .
| .
+----------------------------- Elements

Perceptron networks (single layer neural networks)

Suppose that a neuron connects with m other neurons and so receives m-many inputs "x1 …. … xm".

A perceptron models a neuron by taking a weighted sum of inputs and sending the output 1, if the sum is greater than some adjustable threshold value (otherwise it sends 0.

The inputs (x1,x2,x3..xm) and connection weights (w1,w2,w3..wm) in Figure 4 are typically real values, both postive (+) and negative (-). If the feature of some xi tends to cause the perceptron to fire, the weight wi will be positive; if the feature xi inhibits the perceptron, the weight wi will be negative.

The Learning Rule

Learning is the process of modifying the weights and the bias.

The learning rule can be summarized in the following two equations:

b = b + [ T - A ]

For all inputs i:

W(i) = W(i) + [ T - A ] * P(i)

Where W is the vector of weights, P is the input vector presented to the network, T is the correct result that the neuron should have shown, A is the actual output of the neuron, and b is the bias.

Training

An entire pass through all of the input training vectors is called an epoch.

Vectors from a training set are presented to the network one after another.

The weights and biases are updated using the perceptron learning rule (as shown above). When each epoch of the training set has occured without error, training is complete.

Sources:

Standard Deviation applied to sorting

Another simple scoring function explained: Sorting by Relative Popularity.

Take a set of values, and figure out the average value for that set (also known as the arithmetic mean). The standard deviation simply tells us by how much the value of the typical element in our set deviates from the average.

Z-Table thoughts

Recently I found a simple implementation of the Cumulative Normal Distribution function in Objective C:

#import <math.h>
#import <stdio.h>

double std_norm_dist_cumulativeNormal(double z) { // standard normal distribution (mean = 0, variance = 1)
	return 0.5 * erfc(-z * M_SQRT1_2);
}

double cumulativeNormal(double z, double mean, double variance) {
	return 0.5 * erfc(((mean - z)/sqrt(variance)) * M_SQRT1_2);
}

int main() {
	double left = std_norm_dist_cumulativeNormal(1.60);
	printf("%f\n", left); // 0.945201
	
	double same_thing = cumulativeNormal(1.60, 0, 1);
	printf("%f\n", same_thing); // 0.945201

	double right = std_norm_dist_cumulativeNormal(1.60) - 0.5;
	printf("%f\n", right); // 0.445201

	return 0;
}

You could use cumulative normal function to calculate the Z-Table. But according to How to Use and Create a Z-Table (see How to create a Z-Table (Heavy Math)), it would be inefficient to build the table from scratch.

On percentiles and normal distribution

After reading Ranking Items With Star Ratings, I have been searching more information on standard score (z) calculation:

Summary on normal distribution (see Standard normal percentiles and critical values).
Standard normal distribution and Critical values (percentiles) for the standard normal distribution tables.
Critical Values of z:

Since there are two “tails", the central area is always 1 - 2*(tail area), and the tail area is always 0.5*(1 – central area).

Normal Distribution Calculator.

The normal distribution table, found in the appendix of most statistics texts, is based on the standard normal distribution, which has a mean of 0 and a standard deviation of 1. To produce outputs from a standard normal distribution with this calculator, set the mean equal to 0 and the standard deviation equal to 1.

Z-table (Right of Curve or Left) and Standard Normal Distribution Table:

The process sounds simple—invert the CDF— but many distributions don’t actually have simple inversions.

Star Ratings

Since a long time ago I keep in my backlog the idea of experimenting a little with the credible intervals approach explained in Ranking Items With Star Ratings (the continuation of How Not To Sort By Average Rating).

Although calculating credible intervals (N) in a five star rating system may seem intimidating at first, the use of the approximate formulas for the example distribution assumptions (Uniform, Consensus, Polarized) should be pretty straightforward. And I believe it is a strategy that is worth exploring.