Problem 1: Asymptotic Notation Consider the following functions 27 nlogn 2 logn
ID: 3682612 • Letter: P
Question
Problem 1: Asymptotic Notation Consider the following functions 27 nlogn 2 logn n! loglogn n3 + logn (logn)2 Inn log n 3 2 n rl ()" 3 Group these function so that f(n) and g(n) are in the same group if and only if f(n) O(g(n)) and g(n) O(f(n)), list the groups in increasing order. Problem 2: Recurrences 2.1 Give an asymptotic upper and lower bounds for the following recurrences: (a) T(1)-1,7(2)-6, and vn 3, T(n)s T(n-2) + 3n + 4 (b)T(1) 1, vn 2 2,T(n) TO+1 (c) T(h) = c vn 10,7(n)-3T() + log2n otherwise (d) T(n) cvn 10,T(n)=T() +2n otherwise (e) T(n)=c vn 10.7(n)-7(vn) +6(loglogn) otherwise (f) T(n)=c vn 10,7(n)=T()m(?) +(n) otherwise 2.2 prove that the asymptotic solution of the recurrence relationExplanation / Answer
Basically, the running time of an algorithm when the input size n is large enough so that constants and lower-order terms do not matter. This is called aymptotic analysis of algorithms.
Now to formalize this idea (It is easy to see that n+2 n, or that
4n^2+3n+10 n^2.
But how about more complicated functions? say n^n + n! + nlog log n + n1/logn).
To express rate of growth of a function:
k1n + k2 n
k1n log n n log n
k1n^2 + k2n + k3 n2
To formalize that a e.g. n log n algorithm is better than a n^2 algorithm.
O-notation (Big-O)
-notation
-notation
O-notation (Big-O)
O(g(n)) = {f(n) : c, n0 > 0 such that f(n) cg(n) n n0}
O(·) is used to asymptotically upper bound a function.
Think of f(n) O(g(n)) as corresponding to f(n) g(n).
Examples:
-notation (big-Omega)
(g(n)) = {f(n) : c, n0 > 0 such that cg(n) f(n) n n0}
(·) is used to asymptotically lower bound a function.
Examples:
-notation (Big-Theta)
(g(n)) = {f(n) : c1, c2, n0 > 0 such that c1g(n) f(n) c2g(n) n n0}
(·) is used to asymptotically tight bound a function.
If f(n) O(g(n)) and f(n) (g(n)) then f(n) (g(n)).
Examples:
1.To find n0, c1, c2 such that c1n log n 6n log n+n log2 n c2n log n for n>n0 c1n log n 6n log n + n log2 n n n .
If we choose c1 = 6 and n0 = 1. 6n log n + n log2 n c2n log n 6 + log n n c2. Is it ok to choose c2 = 7? Yes, log n n if n 2.
2.So c1 = 6, c2 = 7 and n0 = 2 works.
Example: Show that 2n^2 + 3n + 7 O(n^2)
Upper and lower bounds are symmetrical: If f is upper-bounded by g then g is lower-bounded by f and we have:
f O(g) g (f)
Example: n O(n^2) and n^2 (n)
An O() upper bound is not a tight bound. Example:
2n^2 + 3n + 5 O(n^100)
2n^2 + 3n + 5 O(n^50)
2n^2 + 3n + 5 O(n^3)
2n^2 + 3n + 5 O(n^2)
Similarly, an () lower bound is not a tight bound. Example:
2n^2 + 3n + 5 (n^2)
2n^2 + 3n + 5 (n log n)
2n^2 + 3n + 5 (n)
2n^2 + 3n + 5 (lg n)
An asymptotically tight bound for f is a function g that is equal to f up to a constant factor: c1g f c2g, n n0. That is, f O(g) and f (g).
For example
Put these functions in order so that if f(n) O(g(n)) (i.e. f(n) is Big-Oh of g(n)), then f(n) appears before g(n) in the list. Group together functions that have the same asymptotic order of growth (i.e. f(n) g(n)).
n ^2 , n log n, n^3 + log n, n, n^2 + 2n log n,
log log n, 17 log n, 10n ^(3/ 2) , n^5 – n^ 4 + 2n,
5n^ 2 log log n, 3n ^2 + n^ 3 log n, n + 6 log n
Solution: Here is the list, where the functions grouped together having the same asymptotic order of growth (there’s only one such pair):
log log n, 17 log n, n, n + 6 log n, n log n,
10n^( 3/ 2) , {n 2 , n2 + 2n log n}, 5n^ 2 log log n,
n^ 3 + log n, 3n^ 2 + n ^3 log n, n^5 n ^4 + 2n
Essentially, most of these can be demonstrated using the fact that log n n for all n 1, and hence, log log n log n (for all n 2, why the change to n 2 ??).
Also, we know that log n n for all n 1. If you know any calculus, this is easy to prove. First show that limn log n n = 0 using L’Hˆopital’s Rule. This means that log n is Little-Oh of n, and, as mentioned in class, this implies that log n is Big-Oh of n. (I basically said that you an assume the fact that log n is Big-Oh of n, and that log n is Big-Oh of n 1 k for all k 1.)
We can easily make statements like 2n log n 2n^ 2 2n ^2 log log n for large enough n. Similarly, n^ 3 log n n^ 4 n^ 5 n ^4 for “large enough” n. These statements can be more formally proved. Recall also that n ^(3 /2) = n · n (1/ 2) = n · n.
note-the above explanation with examples can help to answer the given question