It's O(1) for both list and tuple. They are both morally equivalent to an integer indexed array.

It is an O(N) operation, tuple(list) simply copies the objects from the list to the tuple. SO, you can still modify the internal objects(if they are mutable) but you can't add new items to the tuple.

Copying a list takes O(N) time.

>>> tup = ([1, 2, 3],4,5 ,6)
>>> [id(x) for x in tup]
[167320364, 161878716, 161878704, 161878692]
>>> lis = list(tup)

Internal object still refer to the same objects

>>> [id(x) for x in lis]
[167320364, 161878716, 161878704, 161878692]

But outer containers are now different objects. So, modifying the outer objects won't affect others.

>>> tup is lis
False
>>> lis.append(10)
>>> lis, tup
([[1, 2, 3], 4, 5, 6, 10], ([1, 2, 3], 4, 5, 6)) #10 not added in tup

Modifying a mutable internal object will affect both containers:

>>> tup[0].append(100)
>>> tup[0], lis[0]
([1, 2, 3, 100], [1, 2, 3, 100])

Timing comparison suggest list copying and tuple creation take almost equal time, but as creating a new object with new properties has it's overhead so tuple creation is slightly expensive.

>>> lis = range(100)
>>> %timeit lis[:]
1000000 loops, best of 3: 1.22 us per loop
>>> %timeit tuple(lis)
1000000 loops, best of 3: 1.7 us per loop
>>> lis = range(10**5)
>>> %timeit lis[:]
100 loops, best of 3: 2.66 ms per loop
>>> %timeit tuple(lis)
100 loops, best of 3: 2.77 ms per loop

TLDR: Your time complexities are correct, though your O(n^3) space for the recursive gen_seq is too pessimistic (it is still significantly more wasteful). Note that the optimal static solution is O(n^2), since that is the size of the answer. If no static answer is required, space complexity can be lowered to O(1).

Let's start by establishing some basic complexities. The below applies to both time and space complexity:

• Creating a character literal is O(1).
• Creating a tuple of size n is O(n).
  • Creating an empty or single-element tuple is O(1).
• Concatenating two tuples of length n and m is O(n+m).
  • Concatenating two tuples of length n^2 and m, it is O(n^2+m) = O(n^2).

Iteration:

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (i-1)*('F',)  # note: `i-1` instead of `n-1`
        seq += side + side + ('F',)
    return seq

Key points for complexity are:

• The range(const, n+1) loop is O(n) time complexity, and O(1) space.
• The side is constructed anew at a size of n for i->n. Space is reused, for a maximum of O(n) space. Time is consumed on all n iterations, for O(n*n) = O(n^2) time.
• The seq is concatenated with an n-tuple on all n iterations. Space is reused, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n^2) = O(n^3) time.

The largest complexity wins, so iteration uses O(n^2) space and O(n^3) time.

Recursion:

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

Key points for complexity are:

• Recursion is repeated from n->1, meaning O(n) time.
• The side is constructed anew at a size of n. Space is not reused, since each side is constructed before recursion, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n) = O(n^2) time.
• The return value is concatenated with an n-tuple on all n iterations. Space is reused, since each return value is constructed after recursion, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n^2) = O(n^3) time.

The largest complexity wins, so iteration uses O(n^2) space and O(n^3) time.

The limit for your time complexity is that the result of each step must be repeated in the next. In Python, this can be circumvented using a generator - this allows you to return intermediate results and proceed with generating more results:

def gen_seq(n):
    yield 'F'
    for i in range(1, n):
        yield 'T'
        yield from ('F' for _ in range(i))
        yield 'T'
        yield from ('F' for _ in range(i))

seq = tuple(gen_seq(m))

Key points for complexity are:

• The range(n) loop is O(n) time complexity, and O(1) space.
• The yield from ... range(i) loop is O(n) time, and O(1) space. Space reuse leaves this at O(1) space. Repetition by n times gives O(n*n) = O(n^2) time.
• Concatenating all results at once via tuple is O(n^2 * 1) = O(n^2) space.

The largest complexity wins, so iteration uses O(n^2) space and O(n^2) time. If the result is not stored but directly used, only O(1) space is used.

Consider a tuple to be just a 'frozen list'. A tuple, like a list, has to be searched through entry by entry in order to find whether an object is a member of that tuple.

Complexity for a membership test is identical to that of a list: O(n).

The reason why dicts and sets are O(1) is that entries are accessed via a hashing algorithm.