script

Friday, January 11, 2013

6.2-6


6.2-6 Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is $\Omega (lg n)$. (Hint: For a heap with n nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf.)

The worst case occurs when an element from root is less than all it children for MAX-HEAPIFY. The running time is $\theta (h)$ where h is height of the tree. h is also log n. hence the running time $\theta(log n)$. The worst case running time is $\Omega (log n)$. since $\Omega$ is not tied to best case running time and $\theta$ is not average case running time and $O$ is not worst case running time. These are just math functionns that specify the bound. The wrost case running time means in a worst case the guarantee that the algorithm will always finish on time.
Also according to theorem 3.1 if $f(n) = \theta(g(n))$ then $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. please refer for more info on asymptotic notations: http://www.cs.berkeley.edu/~jrs/61b/lec/21

No comments:

Post a Comment