title: What is Python 3 `str.__getitem__` computional complexity?
body: <pre><code>''' Set up '''
  s= open(&quot;Bilion_of_UTF-8_chars.txt&quot;,encoding=&quot;UTF-8&quot;).read()
  
  '''
  The following doesn't look like a cheap operation
  because Python3 `str`-s are UTF-8 encoded (EDIT: in some implementations only).
  '''
  my_char= s[453_452_345]
  </code></pre>
  <p>However, many people write loops like this:</p>
  <pre><code>for i in range(len(s)):
      do_something_with(s[i])
  </code></pre>
  <p>using indexing operation up to n times or more.</p>
  <p>How does Python3 resolve the problem of indexing UTF-8 characters in strings for both code snippets?</p>
  <ul>
  <li>Does it always perform a linear look-up for nth char (which is both simple &amp; expensive resolution)?</li>
  <li>Or maybe it stores some additional C pointers to perform smart index calculations?</li>
  </ul>