|
-
June 15th, 2009, 05:54 PM
#1
Finding maximum in a Hashtable
Given an Hashtable, is there a way of finding the maximum element in the hashtable in less than O(n) in the worst case where n is the total number of elements in the Hashtable? In other words, is there a way of finding such an element by means other than doing a linear search?
HM
Last edited by humor_me; June 16th, 2009 at 05:44 AM.
-
June 17th, 2009, 05:19 AM
#2
Re: Finding maximum in a Hashtable
A hashtable is unordered, so there is no way to do it faster than O(n).
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
July 7th, 2009, 01:01 PM
#3
Re: Finding maximum in a Hashtable
Depends on the function used for hashing. Also depends on the no of digits of the integers we are using. Typically - a radix sort uses this. Worst case is still O(kN) but think of the best case.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote
