Pieces of mathematics that are relevant for a developer.
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:
This is what logarithm is:
bx = y <=> log b y = x
Important formulas |
---|
eln x = x |
blog b y = y |
loga(x*y) = loga(x) + loga(y) |
ab = eln(a^b) = eb*ln(a) |
The last one can be used for computing an 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:
Square roots of quadratic equation:
d = sqrt(b
2
-4ac)
x = (-b +/- d)/2a
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
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.
n
elements: n!
k
distinct elements from n
(order matters): n!/(n-k)!
k
elements from n
(order matters): n^k
k
distinct elements from n
(order does not matter): n!/k!(n-k)!
(Newton’s symbol)k
elements from n
(order does not matter): (n+k-1)!/k!(n-1)!
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)
.
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: