Get item is getting an item in a specific index, while lookup means searching if some element exists in the list. To do so, unless the list is sorted, you will need to iterate all elements, and have O(n) Get Item operations, which leads to O(n) lookup.

A dictionary is maintaining a smart data structure (hash table) under the hood, so you will not need to query O(n) times to find if the element exists, but a constant number of times (average case), leading to O(1) lookup.

Accessing primes[i] is done in constant time, O(1). What that means is that the time needed to read primes[i] does not increase as the primes becomes bigger and that it does not increase when i becomes bigger. In layman's terms: it's damn fast!

Then again, accessing a local variable p is still faster than accessing primes[i], because the latter has to look up and call the __getitem__ implementation of the primes object. Therefore caching a value in a local variable instead of looking up a list twice is marginally faster.

On the other hand, caring about marginal speed improvements is meaningless compared to reducing algorithm complexity. For the problem of finding prime numbers, you should focus on finding a smart algorithm rather than on improving built-in-list access times.

Python's [] is implemented as an array, not a linked list. Although resizing is O(n), appending to it is amortized O(1), because resizes happen very rarely. If you're not familiar with how this works, read this Wikipedia entry on dynamic arrays. Python's list doesn't expand by a factor of 2 each time, it's a bit more complicated than that, but the expansions are still designed to make appending amortized O(1).

Inserting in the middle, however, is always an inefficient O(n), because n items may have to be moved.

Tuples aren't faster than lists - they're just immutable lists under the hood (*).

Regarding your dictionary test: depending on your exact implementation, caching in a list will be faster than with a dict. However, Python's dicts are highly optimized, and especially for small amounts of keys will perform great.

(*) Here's a list's "get item" C function in Python 2.6:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL)
            indexerr = PyString_FromString(
                "list index out of range");
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
}

And this is a tuple's:

PyObject *
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
{
    if (!PyTuple_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        PyErr_SetString(PyExc_IndexError, "tuple index out of range");
        return NULL;
    }
    return ((PyTupleObject *)op) -> ob_item[i];
}

As you can see, they're almost exactly the same. In the end, after some type and bound checking, it's a simple pointer access with an index.

[Reference: Python documentation on Time Complexity for data type operations]

Every Python value, be it an object, tuple, int, or None, is represented as a PyObject* in C. Because this is a pointer, all these values have the same size (even if the PyObject structure may have different sizes, depending on what it represents). (See: Include/object.h)

So a Python list internally holds a C array of type PyObject**, which allows O(1) access along the ordinary C rules. (See: Include/listobject.h, and PyList_GetItem() in Objects/listobject.c)

This technically only holds for the CPython reference implementation, but other implementations will be similar. The crucial point is that the Python language defines its own data model and type system that does not fit directly into the C type system.

Because using Python objects can be wasteful, the NumPy library provides densely packed arrays. But these now have an explicit type for all values. If you have a NumPy ndarray of type float, you cannot store ints in that array.

there is a very detailed table on python wiki which answers your question.

However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so:

for i, item in enumerate(some_seq):
    bar(item, i)