Question

Explain how to measure the efficiency of an algorithm

Answer 1

Time efficiency - a measure of amount of time for an algorithm to execute. Space efficiency - a measure of the amount of memory needed for an algorithm to execute. Asymptotic dominance - comparison of cost functions when n is large. That is, g asymptotically dominates f if g dominates f for all "large" values of n.

Answer 2

Take two non -ve functions f and g, f = O(g) if & only if g asymptotically dominates f
"f is of the order g" or "The order of f is g"
Formally, if f(n) and g(n) are functions defined for -ve integers then f(n) = O(g(n))
if there exists a c such that |f(n)| <=c|g(n)| for all sufficiently large positive integers n
for example
We want to show that n2 dominates the polynomial 3n2 + 3n + 10, or, in other words
3n2 + 3n + 10 = O(n2)
Let c = 4 (there are lots of c's to choose from) and show that there exists an n0 in which the equation holds
3n2 + 3n + 10 <=4n2 0 <= n2-3n-10 0 <= (n-5)(n+2)
so for n >= 5 we found c=4