Average Case Complexity of a function

What is the average case complexity of the following function given that the input is a set of independent uniform natural numbers.

def d(a):    
    for i in range(len(a)):
        if a[i] == 0 or a[i] == 1:
            for j in range(i+1, len(a)):
           开发者_Go百科     if not (a[j] == 0 or a[j] == 1):
                    swap(a, i, j)
                    break

What do you think, how to approach this problem in mathematical terms?

---

Leaving out all the details, we get two nested loops, indicating a quadratic algorithm. Taking the if into account, such a small percentage of numbers actually execute the inner loop that the average case is effectively linear.

---

for i in range(len(a)):

The result will be the length of a multiplied with the average time for any index in range(len(a)) (let's ignore the break for now).

if a[i] == 0 or a[i] == 1:

Two accesses of the values of a, so let's add 2 * [time to retrieve a[i]]. The probability that a value of a(an element of an infinite set, ℕ) is an element of any finite set(such as {0,1}) is infinitely close to zero. Since the further code inside takes finite time, we can safely ignore it.

Average case complexity: 2 len(a) [time to retrieve a[i]] ∈ Θ(len(a)) ⊂ O(len(a)).