Question: I can imagine only two cases: as 2^k approaches n, (say, if 2^k == n), then the number of steps required is n / n, or 1, so it has a run-time of O(1).

However, if 2^k is small, (say, if 2^k == 1), then n steps are required, so it has a run-time of O(n).

In essence, if 2^k can be written in terms of n, then the number of steps required is an integer, so it has a run-time of O(1). If 2^k cannot be written in terms of n, it has a run-time of O(n).

Both of these cases are worst-case; for any unknown and possibly large n, these run-times still hold. Is there any situation in which 2^k can't be qualified as much smaller than n *or* close to n?

Imagine you were to write a (possibly very long) table containing the run-times for the function for values of k such that (n / 2^k) >= 1. As k starts at 0 and increases, the run-times are O(1), but as k starts at a large value and decreases, the run-times are O(n). Is there a theoretical point at which the run-time switches from O(1) to O(n)?

Or am I simply not grasping the "main idea" of Big-O analysis?

EDIT: A linear search is assumed

Answer: 
You are micro-optimising, you should not worry about how many string objects are created there. A few string objects here and there are not going to affect the memory footprint to any noticeable extent, and as you are touching the filesystem here, any performance gains from one look-up method over another is going to melt into insignificance compared with waiting for I/O to complete. Instead, focus on readability and maintainability.

Your example could be simplified further:

```
project_dir = os.path.join(item_number, 'Project')
os.makedirs(os.path.join(project_dir, 'Images'))
os.makedirs(os.path.join(project_dir, 'Area Templates'))

```

The intervening directories will be created for you, there is no need to call `os.makedirs()` quite so often.

CPython can and will re-use immutable objects created from literals, such as tuples and strings, *within the same codeobject*. That means that if you used `'Project'` multiple times in one function, then Python can opt to only store one such object in the code-object constants:

```
>>> def demo():
...     project = "Project"
...     os.makedirs(os.path.join(item_number, project))
...     os.makedirs(os.path.join(item_number, project, 'Images'))
...     os.makedirs(os.path.join(item_number, project, 'Area Templates'))
...
>>> demo.__code__.co_consts
(None, 'Project', 'Images', 'Area Templates')

```

See [About the changing id of a Python immutable string](https://stackoverflow.com/questions/24245324/about-the-changing-id-of-a-python-immutable-string/24245514#24245514) for the full details. You should *not* rely on this behaviour however.
Yes, the strings are the same. Try this

```
a = 'project'
b = 'project'
a is b # True

```

This is safe, since strings are immutable, and changing any of them creates a new string, so other variables holding the same value are not affected