0

In Python, if we need to find the maximum element from the list. We use :

>>>max(listname) to get the maximum number from the list. 
Time Complexity : O(1)

If we use C/C++, 

we need to iterate over the loop and get the max.
Time Complexity: O(n) or O(n square)

Hence, does the time complexity changes over the programming language?

Drool
  • 119
  • 1
  • 7

1 Answers1

1

No. max(listname) is always O(N) where N is the length of listname (*). This is just by definition of complexity - because the iteration has to happen somewhere - maybe in your code (in case of your C/C++), or maybe in library code (in case of Python).

Sometimes we ignore some complexity, usually because it is beneath our notice; for example, x * y in Python (with x and y being integers) is actually not O(1), because x and y are of arbitrary length in Python, and the * operation thus does execute in loops, but we do simplify and treat it as O(1), as it is most often the case that the integers are of small enough size for it not to matter.

The choice of programming language only matters inasmuch as it affects our perception of what we can ignore; but it does not actually change the time complexity.

*) it is only O(N) in case N is proportional to input size; it is O(1) if it is known in advance, or limited. For example, lst = read_list(); m = max(lst) is O(N), but lst = [1, 2, 3, 4]; m = max(lst) is O(1), as is lst = read_list(); lst = lst[:4]; m = max(lst).

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • Thanks. Can you please clarify the last point where the time complexity differs in read_list() and explicitly mentioning the list. – Drool Dec 25 '18 at 06:25
  • 1
    If we know N = 4, then O(N) is actually O(4) = O(1). I.e. if we're limited to 4 elements, then we are running in "constant time" - even if this constant time is longer than the constant time for one element. The only way to get O(N) is for N to not be known or limited. Time complexity is the measure of how an algorithm scales with input size. If you input 100 elements, the search is 10 times longer than when you input 10 elements, yes? But if you only search through the first 4 elements, then it doesn't matter if you input 10 or 100: the search time is equal. This is "constant time" - O(1). – Amadan Dec 25 '18 at 06:31