# Question: Is the function lg n Polynomially bounded

Is the function ⌈lg n⌉! Polynomially bounded? Is the function ⌈lg lg n⌉! Polynomially bounded?

**View Solution:**## Answer to relevant Questions

Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + cn, where c is a constant, is Ω(n lg n) by appealing to a recursion tree.Use indicator random variables to solve the following problem, which is known as the hatcheck problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hatcheck person gives the hats back to the ...What are the minimum and maximum numbers of elements in a heap of height h?Why do we analyze the average-case performance of a randomized algorithm and not its worst-case performance?Show that the second smallest of n elements can be found with n + ⌈lg n⌉ - 2 comparisons in the worst case.Post your question