0

implementation of Stoi function can be seen here

what is time complexity of above mentioned stoi function?

Tarun Jain
  • 411
  • 5
  • 17
  • Theoretically it is O(n) where n is the length of the string. However since integers are bounded in size (a 32-bit integer can be represented with at most 11 chars in base10 form) it is actually O(1). – freakish Sep 01 '21 at 08:45
  • thanks for answer but i didn't understand that bounded in size thing if possible can you please explain in a bit more detail ? Thank you – Tarun Jain Sep 01 '21 at 08:49
  • 1
    A 32-bit integer is in range -2147483648 to 2147483647. And so a 32-bit integer has at most 11 chars. Thus given a string it is enough to check first 11 characters to verify whether it is a valid 32-bit integer or not. And so the complexity is O(1) - it doesn't depend on the size of the string. – freakish Sep 01 '21 at 08:51
  • 3
    As is common with geeksforgeeks, that page has it wrong - there's no implementation of that function there. That site is a waste of time and not worth what you're paying for it. Get a [good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – molbdnilo Sep 01 '21 at 08:52
  • @freakish you can have 32 characters of base 2 string fit in a 32 bit integer – Caleth Sep 01 '21 at 08:55
  • 1
    @Caleth sure, I only considered base10. Regardless the number of chars to be verified is always bounded. – freakish Sep 01 '21 at 09:00

1 Answers1

5

The time complexity of std::stoi is unspecified. A conforming implementation can use any algorithm that eventually generates the correct result.

As a quality-of-implementation issue, it will probably do a linear scan through at most logbase(INT_MAX) + 3 digits, which is bounded above by sizeof(int) * CHAR_BIT. That's O(1), but there might be any amount of preceding whitespace, so it's probably O(str.size())

Caleth
  • 52,200
  • 2
  • 44
  • 75