For a list li, I want to print only the values of the triplets a, b, c where 0 <= index(a) < index(b) < index(c) < len(li).Example:f([6, 3, 88, 4])6 3  886 3  46 88 43 88 4 Here is my solution, but it is O(n**3) (time complexity):def f(li):    for i, n in enumerate(li):        for j, o in enumerate(li):            for k, p in enumerate(li):                if i < j < k:                    print n, o, pHowever, it should be doable in O(n). Any clues?I have the following function as well:def f(li):    i = 0    j = i + 1    k = j + 1    n = li[i]    o = li[j]    p = li[k]    while i < j < k:        print n, o, p        if n == li[-3]:            break        if p != li[-1]:            k += 1        elif o == li[-2]:            i += 1            j = i + 1            k = j + 1        elif p == li[-1]:            j += 1            k = j + 1        n = li[i]        o = li[j]        p = li[k]I believe this is O(n).
Extracting length-3 subsequences from a list
python;comparative review;complexity
In any case, the minimum time complexity for a list of length \$n\$ would be $$\mathrm{nCr}(n, 3) = \frac{n!}{3!\ (n-3)!} = \frac{1}{6} n(n - 1)(n - 2)$$ because that is the number of results to expect.  That is \$O(n^3)\$.Explanation of the combination formula:Let's ignore the i < j < k requirement for now.  How many ways are there to pick one element?  (There are \$n\$ ways.)  How many ways are there to pick the next element from the remaining \$n-1\$ elements?  (For each of the \$n\$ first picks, there are \$n-1\$ second picks.)  How many choices are there for the third element?  (There are \$n-2\$.)  That means that there are \$n(n-1)(n-2)\$ permutations when picking 3 elements from a list of \$n\$, also written as \$\frac{n!}{(n-3)!}\$.Now, let's consider the ordering.  For any collection of 3 items, how many possible sequences exist?  There are 3 choices for the first item, 2 choices for the second item, and 1 obligatory choice for the third.  That's \$3!=3\cdot2\cdot1=6\$ orderings.  So, out of all the \$n(n-1)(n-2)\$ lists of of \$i, j, k\$, only \$\frac{1}{6}\$ of the them will have \$i, j, k\$ in ascending order.What you can do, though, is eliminate the conditional, so that every iteration succeeds in producing a result.  (Your if i < j < k check succeeds less than \$\frac{1}{6}\$ of the time.)  I would also change print to yield for greater flexibility.def subsequence_triplets(lst):    end = len(lst)    for i in range(0, end - 2):        for j in range(i + 1, end - 1):            for k in range(j + 1, end):                yield lst[i], lst[j], lst[k]for a, b, c in subsequence_triplets([6, 3, 88, 4]):    print a, b, c