Discrete maths in Pinterest (Algorithms)

Properties of Algorithms

Input -An algorithm has input values from a specified set.

Output -From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.

Definiteness -The steps of an algorithm must be defined precisely.

Correctness -An algorithm should produce the correct output values for each set of input values.

Finiteness -An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.

Effectiveness -It must be possible to perform each step of an algorithm exactly and in a finite amount of time.

Generality -The procedure should be suit for all problems of the desired form, not just for a particular set of input values

Complexity in algorithms

Big Oh (O)

Big Oh is often used to describe the worst-case of an algorithm by taking the highest order of a polynomial function and ignoring all the constants value since they aren’t too influential for sufficiently large input.

Big Omega (Ω)

Big Omega is the opposite of Big Oh, if Big Oh was used to describe the upper bound (worst-case) of a asymptotic function, Big Omega is used to describe the lower bound of a asymptotic function. In analysis algorithm, this notation is usually used to describe the complexity of an algorithm in the best-case, which means the algorithm will not be better than its best-case.

Big Theta (Θ)

When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O(n log n) and Ω(n log n), it’s actually has the complexity Θ(n log n), which means the running time of that algorithm always falls in n log n in the best-case and worst-case.