Time complexity of dictionary lookup in Python
<p>I have a function that builds substrings given a string recursively. Could anyone please tell me what's the complexity of this? I'm guessing it's O(2*<em>n), because given an input of n, there can be 2</em>*n substrings, but i'm not 100% sure.</p>

<p>Here's the code:</p>

<pre><code>def build_substrings(string):
    """ Returns all subsets that can be formed with letters in string. """
    result = []
    if len(string) == 1:
        result.append(string)
    else:
        for substring in build_substrings(string[:-1]):
            result.append(substring)
            substring = substring + string[-1]
            result.append(substring)
        result.append(string[-1])
    return result
</code></pre>

<p>I actually have on more question that i think doesn't deserve a new topic. I was wondering what's the complexity of searching a key in a dictionary in Python(if item in dictionary)?
Thank you alot for your help! </p>
