Question

1. Asymptotic Bounds la) Rank the following functions at ascending order; that is, find an arrangement fi, f2,..., fg of the functions satisfying f1 = O(f2), fz = O(fz), ...,f7= O(fy). Briefly show your work for this problem. (2pts) Ign n n n? (lg n) len 21gn n? +n nlgign 1b) Partition your list into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n) = (g(n)). (2pts)

Answer 1

1)

The order is given as:

• 1
• (lg n)^ lg n
• n^(1/ lg n)
• n
• 2^{lg n}
• n²
• n² + n
• n^{lg lg n}

NOTE: As per HOMEWORKLIB POLICY I am allowed to answer specific number of questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.