1

If I would like to know other built-in function's time complexity, what are the ways to figure it out except for looking for cheatsheet

Chloe
  • 83
  • 1
  • 6
  • Think about what is the input. For a string - how would you check if it's a digit without looking at all N characters? And there's no reason to look at any more than once – OneCricketeer Oct 10 '20 at 23:38
  • This post https://stackoverflow.com/questions/11253955/how-to-check-source-code-of-a-python-method can tell you where to find the source code, and the source code for many python builtins lives there. As for `isdigit` specifically, you will find that it uses the `isdigit` function from the C standard library. So finding the time complexity of that function would answer your question. – tclarke13 Oct 11 '20 at 00:02

1 Answers1

3

Think about what you're actually trying to do, verifying that the string is a digit. The only way to be 100% sure about that is by making sure every character in the string is a digit, therefore it needs to evaluate every character.

Therefore it has a linear time complexity, O(n), where n is the length of the string

feverdreme
  • 467
  • 4
  • 12