Table of contents

• Summations
• Logarithms
• Quadratic Equation
• Trygonometry
• Prime numbers
• Combinatorics
• Probability
  • Conditional probability

Summations

This is called a summation, more specifically arithmetic progression:

because mathematical induction. Important to remember, as this means that the complexity of an algorithm that takes i steps with every iteration from i=0..n has complexity of Θ(n^2) (big theta). This is the case of selection sort. And the generified rule is:

for p>=1.

Geometric series have the index of the loop involved in the exponent:

for for a>1.

What may be also relevant is this factorial formula:

Logarithms

This is what logarithm is:

b^x = y <=> log _b y = x

The last one can be used for computing aⁿ fast. We just make a recursive function that will compute the squares or “squares + 1” of the previous result, and that is just O(lg(n)).

Harmonic summation is another important formula:

Quadratic Equation

Square roots of quadratic equation:

• d = sqrt(b2-4ac)
• x = (-b +/- d)/2a

Trygonometry

Area of a triangle:

• 1/2 * a * h, h is the height of the triangle measured from a
• 1/2 * a * b * sin(α), α is the angle between a and b

Prime numbers

Every positive integer can be decomposed into a product of primes.

Sieve of Eratosthenes is an algorithm to fins all prime numbers up to a given max value: in a sorted list starting from 2 we take each number and count it as prime, and cross out all following numbers that are divisible by this number.

We can also ask for testing whether a number is prime.

Combinatorics

• Number of possible permutations of n elements: n!
• Number of possible variations of k distinct elements from n (order matters): n!/(n-k)!
• Number of possible variations of k elements from n (order matters): n^k
• Number of possible combinations of k distinct elements from n (order does not matter): n!/k!(n-k)! (Newton’s symbol)
• Number of possible combinations of k elements from n (order does not matter): (n+k-1)!/k!(n-1)!

Probability

What is the probability that out of 3 consecutive tries 2 are successful, if each try has probability p of being successful?

Answer: p*p*(1-p).

Conditional probability

• P(A and B) = P(B given A)*P(A)
• P(A or B) = P(A) + P(B) - P(A and B)

But:

For A and B independent (A happening tells me nothing about B happening):

• P(A and B) = P(A) * P(B)

For A and B mutually exclusive (if A happens B cannot happen:

• P(A or B) = P(A) + P(B)

*Only impossible events are both mutually exclusive and independent.

Comments

Comments: