Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms (RECURSIVE ALGORITHMS (Recursive Function. A recursive function…
Algorithms
RECURSIVE ALGORITHMS
Recursive Function. A recursive function is a function that calls itself again and again to solve a problem
-
-
PSEUDO CODE
This algorithm finds the smallest of the numbers x, y and z.
Input: x, y, z
Output: Min [the minimum of x, y and z]
-
-
-
If (y < Min) // is y smaller than Min, update Min
-
If (z < Min) // is z smaller than Min, update Min
-
-
-
-
-
BIG-OH (O) NOTATION
function f(n) = O(g(n)) (read as "f of n is big oh of g of n") iff there exist two positive constants C and no such that f(n) ≤ C × g(n) for all n, n ≥ no.
-
The term O(1) to mean a computing time that is constant,
OMEGA (Ω) NOTATION
function f(n) = Ω (g(n)) (read as "f of n is omega of g of n") iff there exist two positive constants C and no such that f(n) ≥ C g(n) for all n, n ≥ no
-
The omega notation provides a lower bound on the value of f(n). For the statement f(n) = Ω(g(n)) to be informative, g(n) should be as large a function of n as possible for which the statement f(n) = Ω(g(n)) is true. Thus we generally say that 4n + 3 = Ω(n), we almost never say that 3n + 3 = Ω(1), even though this is correct. Therefore g is an asymptotic lower bound for f.
THETA (θ) NOTATION
The function f(n) = θ(g(n)) (read as "f of n is theta of g of n") iff there exist three positive constants C1, C2 and no such that C1g(n) ≤ f(n) ≤ C2g(n) for all n, n ≥ no
The theta notation is more precise than both the big-oh and omega notations. The function f(n) = θ(g(n)) iff g(n) is both an upper and lower bound on f(n). Therefore g is an asymptotic tight bound for f.
-
