estimating a big O for possible arbitrary iterations

18 Views Asked by At

Consider a question of devising an algorithm to find if there are disjoint sets of the subset of the set S={1,2,3,4,.....n} , S1,S2,S3...Sn.

Now I device such an algorithm (in pseudocode):

procedure: {finding disjoint sets in Si, i|i=1.....n}

for i in 1 to n:
    for j in 1 to LengthOf(Si):
        k := j+1
        disjoint := true
        while k <= LengthOf(Sj):
            if(Sj[k]==Si[j]):
            disjoint := false
            k +=1

if disjoint:
    yes disjoint exists
else:
    no disjoint    

Now, how can we give a big O estimate of such an algorithm. The number of times the iteration is done is not fixed and depends on the length of the sets. Even there are three levels of iterations, which would otherwise suggest a O(n3) worst case complexity, here it is not the case that each inner loop goes on n times, so, is it really O(n3)? If so, please explain me how?