Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course.
Now we are going to be less precise and worry only about approximate answers for large inputs.
The
Definition: Let f(n) and g(n) be realvalued
functions of a single nonnegative integer argument.
We write f(n) is O(g(n)) if there is a positive real
number c and a positive integer n_{0}
such that f(n)≤cg(n) for all n≥n_{0}.
What does this mean?
For large inputs (n≤n_{0}), f is not much bigger than g (f(n)≤cg(n)).
Examples to do on the board
Theorem (arithmetic): Let d(n), e(n), f(n), and g(n) be nonnegative realvalued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and e(n) is O(g(n)). Then
Theorem (special functions): (Only n varies)
Definitions: (Common names)
1.2.2
Definition: Let f(n) and g(n) be real valued functions of an integer value. Then f(n) is Î©(g(n)) if g(n) is O(f(n)).
Remarks:
Remarks We pronounce f(n) is Î˜(g(n)) as "f(n) is bigTheta of g(n)"
Examples to do on the board.
If you remember limits from calculus, what we want is that f(n)/g(n)→0 as n→∞. However, the definition we give does not use limits (it essentially has the definition of a limit built in).
Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is o(g(n)) if for any c>0, there is an n_{0} such that f(n)≤g(n) for all n>n_{0}. This is pronounced as "f(n) is littleoh of g(n)".
Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is Ï‰(g(n) if g(n) is o(f(n)). This is pronounced as "f(n) is littleomega of g(n)".
Examples: log(n) is o(n) and x^{2} is Ï‰(nlog(n)).
Source
https://cs.nyu.edu/courses/fall02/V22.0310002/classnotes.html
Now we are going to be less precise and worry only about approximate answers for large inputs.
The BigOh
Notation
Definition: Let f(n) and g(n) be realvalued
functions of a single nonnegative integer argument.
We write f(n) is O(g(n)) if there is a positive real
number c and a positive integer n_{0}
such that f(n)≤cg(n) for all n≥n_{0}.
What does this mean?
For large inputs (n≤n_{0}), f is not much bigger than g (f(n)≤cg(n)).
Examples to do on the board
 3n6 is O(n). So, what f(n) = 3n6 <= c*n. For example, c=4. Some less common ways of saying the same thing follow.
 3x6 is O(x).
 If f(y)=3y6 and id(y)=y, then f(y) is O(id(y)).
 3n6 is O(2n)
 9n^{4}+12n^{2}+1234 is O(n^{4}).
 innerProduct is O(n)
 innerProductBetter is O(n)
 innerProductFixed is O(n)
 countPositives is O(n)
 n+log(n) is O(n).
 log(n)+5log(log(n)) is O(log(n)).
 12345^{54321} is O(1).
 3/n is O(1). True but not the best.
 3/n is O(1/n). Much better.
 innerProduct is O(100n+log(n)+34.5). True, but awful.
Theorem (arithmetic): Let d(n), e(n), f(n), and g(n) be nonnegative realvalued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and e(n) is O(g(n)). Then
 ad(n) is O(f(n)) for any nonnegative a
 d(n)+e(n) is O(f(n)+g(n))
 d(n)e(n) is O(f(n)g(n))
Theorem (special functions): (Only n varies)
 If f(n) is a polynomial of degree d, then f(n) is O(n^{d}).
 n^{x} is O(a^{n}) for any x>0 and a>1.
 log(n^{x}) is O(log(n)) for any x>0
 (log(n))^{x} is O(n^{y}) for any x>0 and y>0.
Definitions: (Common names)
 If a function is O(log(n)) we call it logarithmic.
 If a function is O(n) we call it linear.
 If a function is O(n^{2}) we call it quadratic.
 If a function is O(n^{k}) with k≥1, we call it polynomial.
 If a function is O(a^{n}) with a>1, we call it exponential.
1.2.2 Relatives
of the BigOh
BigOmega and BigTheta
Recall that f(n) is O(g(n)) if for large n, f is not much bigger than g. That is g is some sort of upper bound on f. How about a definition for the case when g is (in the same sense) a lower bound for f?Definition: Let f(n) and g(n) be real valued functions of an integer value. Then f(n) is Î©(g(n)) if g(n) is O(f(n)).
Remarks:
 We pronounce f(n) is Î©(g(n)) as "f(n) is bigOmega of g(n)".
 What the last definition says is that we say f(n) is not much smaller than g(n) if g(n) is not much bigger than f(n), which sounds reasonable to me.
 What if f(n) and g(n) are about equal, i.e., neither is much bigger than the other?
Remarks We pronounce f(n) is Î˜(g(n)) as "f(n) is bigTheta of g(n)"
Examples to do on the board.
 2x^{2}+3x is Î¸(x^{2}).
 2x^{3}+3x is not Î¸(x^{2}).
 2x^{3}+3x is Î©(x^{2}).
 innerProductRecutsive is Î˜(n).
 binarySearch is Î˜(log(n)). Unofficial for now.
 If f(n) is Î˜(g(n)), the f(n) is &Omega(g(n)).
 If f(n) is Î˜(g(n)), then f(n) is O(g(n)).
LittleOh and LittleOmega
Recall that bigOh captures the idea that for large n, f(n) is not much bigger than g(n). Now we want to capture the idea that, for large n, f(n) is tiny compared to g(n).If you remember limits from calculus, what we want is that f(n)/g(n)→0 as n→∞. However, the definition we give does not use limits (it essentially has the definition of a limit built in).
Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is o(g(n)) if for any c>0, there is an n_{0} such that f(n)≤g(n) for all n>n_{0}. This is pronounced as "f(n) is littleoh of g(n)".
Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is Ï‰(g(n) if g(n) is o(f(n)). This is pronounced as "f(n) is littleomega of g(n)".
Examples: log(n) is o(n) and x^{2} is Ï‰(nlog(n)).
Properties of Notations
Notations

Reflexive

Transitive

Symmetric

Transpose Symmetric

O

Yes

Yes

No

No

Î©

Yes

Yes

No

Yes
Yes i.e. f(n) = O(g(n)), iff
g(n) = Î©(f(n))

Î˜

Yes
i.e.f(n) = Î˜ (f(n)) 
Yes
f(n)=Î˜(g(n)) and
g(n)=Î˜(h(n))
implies f(n) = Î˜(h(n)) 
Yes

No

o

No

Yes

No

No

Ï‰

No

Yes

No

No

Source
https://cs.nyu.edu/courses/fall02/V22.0310002/classnotes.html
0 comments:
Post a Comment