heap question

[RomanRega]

I have some difficulties to get this.

"The construction of a heap from a set of n elements require a time of calculus:

a) O(log n)
b) O(n)
c) O(n^2)
d) O(n log(n))
e) O(h)
"

The correct answer of this test is reported to be O(n). I don't get it.
I would have bet all my money on the O(n log n) answer.

I'm lost. What am I missing?

[Hnefi]

I don't see how it could be possible to build a heap with worst-case complexity less than O(nlog(n)). There is simply no way to get around it. However, I have heard some people claim that in practice, the expected time complexity of a well-trimmed heapify is closer to O(n). But if that is what is meant by the question you quoted, it was a very, very poorly formulated question. Talk to your teacher/professor - it might be a simple typo.

[RomanRega]

Thanks for your help. :)

I have an other question.

Let's say that O(n) is the correct one. Then also the answer O(n log n) or O (n^2) aren't correct too?

And an other one. :)

In the test there is an open question which asks
"Define the sets O, Omega, Theta"

I'm a bit confused about this one. I never considered O, Omega and Theta as sets (as in set theory). I know there is a notation which use the "belongs to" symbol in place of "is" or "=", but i thought it was just a notation.

Am i wrong? Does exists somewhere a definition of O, Omega and Theta as sets? Where I can find it?

[Hnefi]

Thanks for your help. :)
No problem. (shamelessly points to the "Rate Post" button ;) )

Let's say that O(n) is the correct one. Then also the answer O(n log n) or O (n^2) aren't correct too?
Technically, if the function runs in O(n) time then it can also be said to run in O(nlog(n)) or O(n^2) or O(n!) etc, but there is little point in using the definition of Ordo that way. The unspoken assumption when trying to determine the complexity of a function is to use a factor in Ordo which is as small as possible.

So although O(n^2) would be correct, O(nlog(n)) would be "more" correct and O(n) would be as correct as any answer can be.

In the test there is an open question which asks
"Define the sets O, Omega, Theta"

I'm a bit confused about this one. I never considered O, Omega and Theta as sets (as in set theory). I know there is a notation which use the "belongs to" symbol in place of "is" or "=", but i thought it was just a notation.

Am i wrong? Does exists somewhere a definition of O, Omega and Theta as sets? Where I can find it?
O, Omega and Theta can be considered sets only in relation to a particular function. In other words, if you have a function n^2, then O could be said to be the set {O(n^(2+)), ... , O(n!) ...}, Theta could be said to be the set {O(n^2)} and Omega could be said to be the set that is the complement of O.

However, I think they meant something more general in your question. They are probably asking for the definition of the three terms, i.e. how to determine what the sets O, Theta and Omega of any given function f is.

[RomanRega]

No problem. (shamelessly points to the "Rate Post" button ;) )


I just did. Thanks again. :)

[RomanRega]

Maybe i found some paper which actually explaine why it could be O(n).

http://crystal.uta.edu/~gdas/Courses/Courses/Fall2005/advAlgos/student_slides/Week4.ppt

The paper state that the total cost of the operation is
sum{i=1 to i=log(n)} ( (h-i) * 2^i ) , h=log(n)

where "i" naturally is the level we are working on.

I was arrived to a similar conclusion by myself.
I say similar because I think the one on the paper might be wrong and we are still not dealing with a O(n) problem.

If i have to insert one element on an EMPTY heap the time needed is just O(1). There's nothing to reheapify after all :)

After the first one, as i insert an other element, the cost rise, since the height of the tree is rising.
Generalizinig the cost depend on the level i'm inserting to. If i have to insert to the second level i have e cost 2, 3 for the 3rd level and so on, since we are counting the number of possible exchanges to reheapify this thing.

We can express that cost as O(i), where "i" is the level we are inserting to.

But we know also that each level i has 2^i nodes.

This means that the actual cost to insert n elemnets in a empty heap is

sum{i=1 to i=log(n)} ( i * 2^i )

and not

sum{i=1 to i=log(n)} ( (h-i) * 2^i ) , h=log(n)

as you can find in that paper.

This last formula seems to say that as we insert elements the price get down instead to rise.
It doesn't make any sense to me.

In fact, following that formula, we have the maximun cost at the level i=1, where cost is (h-1) per 2 nodes. At the third level we have a cost of (h-2) per 4 nodes and so on.

If we guess to have h=100, we see that the 2 nodes on the sencod level cost 99 (as i need 99 exchages to rehepify such a short heap!), and at the very last i will have 2^100 nodes which cost nothing.

Pretty amazing, huh?. I might be dumb but i dont get it.
What am i missing?

[RomanRega]

I'm discussing this problem in an other forum.

They proposed a different paper which should demostrate again, in a different way, that this is a O(n) problem, so i report it here too, because for me this even more amazing.

The paper is:
http://serghei.net/docs/programming/Cormen/chap07.htm#076a_131e

It says that the number of nodes in a level h of a heap could be demostrated to be n/(2^(h+1)).

I miss the logic of this thing too.

Let's say i have a 100 elements heap. The nodes on the level h=1 must be then

100/(2^(1+1)) = 100/4 = 25.

I can't see how a complete binary tree (as a heap is by definition) can have 25 children under his root.

I always tought that the maximun number of nodes in a level of a binary tree is fixed, and depend on the level, and NOT on the total number of nodes in the tree...

In the paper say that the dimostration of that formula can be found on the exercise 7.3-3.
Well at the exercize 7.3-3 there is only written
"7.3-3
Show that there are at most n/2h+1 nodes of height h in any n-element heap."

Too easy like that :) Where i can find this dimostration?