8

min, max have O(N) time complexity because they have to loop over the given list/string and check every index to find min/max. But I am wondering what would be the time complexity of min,max if used on a set? For example:

s = {1,2,3,4} # s is a set

using min/max we get:

min(s) = 1
max(s) = 4

Since sets do not use indices like lists and strings, but instead operate using buckets that can be accessed directly, does the time complexity of min/max differ than the general case?

Thank you!

abadawi
  • 378
  • 1
  • 5
  • 15
  • 1
    You must still check all elements, or how would the `set` know? If you know up front, that you need the min and max values, you can store them along with your data. However, then you end up with O(log n) when deleting elements. – JohanL Mar 11 '18 at 05:58
  • If they're not sorted set, they're likely O(n). – user202729 Mar 11 '18 at 06:02
  • You may be able to utilize a sorted set to get better than O(n) min max operations: https://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set – Anil Vaitla Mar 11 '18 at 06:15

1 Answers1

7

As pointed out in the comments above, python is a well documented language and one must always refer to the docs first.

Answering the question, according to the docs,

A set object is an unordered collection of distinct hashable objects.

Being unordered means that to evaluate maximum or minimum among all the elements using any means (inbuilt or not) would at least require one to look at each element, which means O(n) complexity at best.

On top of it, max and min functions of python iterate over each element and are O(n) in all cases. You can always look up the source code yourself.

Sean Breckenridge
  • 1,932
  • 16
  • 26
Shivam Tripathi
  • 415
  • 4
  • 13