The heap is constructed by simply inserting the items into the heap one at a time, where the heap insertion algorithm for a min heap is as follows:
The heap is constructed as follows:
Heapify leaves -- no work. Heapify next level -- N/4 nodes, each of which could travel at most 1 level = N/2 Heapify next level -- N/8 nodes, each of which could travel at most 2 levels = 2*N/8 = N/4 Heapify next level -- N/16 nodes, each of which could travel at most 3 levels = 3*N/16 = 3N/16 And so on... total is N*(Sum for i=1..logN of (i-1)/2i) = O(N).
The heapsort algorithm is as follows:
O(N). An arbitrary element could be in either subtree of a heap, so can't do better than traversing the tree and looking at every item.
To search in N elements stored in a hash table of size b, assuming that items are evenly distributed and that linked lists are used from each location, time required is O(N/b). This is because on average N/b items will be stored at each location, and a linear search of those items will be required. If the table size is constant this is O(N); if the table size kN, k>0, this is O(1).
For a good hash function and table size >= 3N/2, open addressing gives O(1) lookup time. The analysis is beyond the scope of this class.
Assume that the trie contains a branch for every bit, not just enough to distinguish from other entries. Then search depends on the length of the bitstring being searched for and is independent of what else is stored in the trie. For example, finding the string 1011001 would always require following 7 branches, regardless of the number of elements in the tree. This is clearly O(1).
Suppose you want to store N items in a binary trie. Then each must have a unique binary representation, which requires log N bits. Since search depends on the length of the bitstring, this is clearly O(log N).