analysis of algorithms Flashcards
sub function
grows slower than the specified function
super function
grows faster than the specified function
ways of measuring efficiency of an algorithm
experimentally
theoretically
experimentally measuring efficiency of an algorithm + problems
by implementing it
problem: different computer, different compiler, all kinds of input
theoretically measuring efficiency of an algorithm + advanatges
analysing the algorithm with mathematical approach
advantages: no implementation needed, independent of the computer or compiler, applies to all possible inputs
big-O notation
expresses asymptotic upper bounds of a function
says that a function grows no faster than a certain rate
f(n) = O(g(n))
f grows no faster than g
=> f is asymptotically less than or equal to g
If f is function, the O(f) is the set of all functions whose orders are _______ that of f.
at most
big-Ω notation
expresses asymptotic lower bounds of a function
says that a function grows at least as fast as certain rate
f(n) = Ω(g(n))
f grows as lest as fast as g
=> f is assimptotically greater than or equal to g
If f is function, the Ω(f) is the set of all functions whose orders are _______ that of f.
at least
big-θ notation
characterises a tight bound
it says that a function grows at a precisely certain rate
If f is function, the θ(f) is the set of all functions whose orders are _______ that of f.
the same as
worst-case and best-case apply to…
inputs to algortihms
upper and lower bounds apply to…
functions
