What is the complexity of this algorithm? I thought it was big O(n) - using only 1 for...in loop

Question

ios project https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates

The algorithm should solve for the top 4 integers in an unsorted array. Here I generate a list of unsorted NSNumbers and iterate over it - maintaining a top 4 list as it goes. I submitted the solution to a code challenge but was told that the solution is not in fact O(n).

// Generate the array self.numbers and unset the top 4 self.topN
// ...
// Use built in fast-enumeration to iterate over array of NSNumbers
    for (NSNumber * num in self.numbers) {
      // Make sure that all 4 of the top4 numbers is initialized
        if(!self.top1){
            self.top1 = num;
            continue;
        }
        if(!self.top2){
            self.top2 = num;
            continue;
        }
        if(!self.top3){
            self.top3 = num;
            continue;
        }
        if(!self.top4){
            self.top4 = num;
            continue;
        }

      // Adjust our top4 as we fly over the array
        if([self.top1 intValue] < [num intValue]){
            self.top1 = num;
            continue;
        }
        if([self.top2 intValue] < [num intValue]){
            self.top2 = num;
            continue;

        }
        if([self.top3 intValue] < [num intValue]){
            self.top3 = num;
            continue;

        }
        if([self.top4 intValue] < [num intValue]){
            self.top4 = num;
            continue;

        }

    }

Update thanks for the quick responses - the issue seems to not be with the complexity of the algorithm but the logic. I was not pushing the numbers down the top 4 when a greater value was found - oops! haha. Here is an updated algorithm for anyone with a similar problem. I'll post my full project solution, too.

for (NSNumber * num in self.numbers) {
      // Make sure that all 4 of the top4 numbers are initialized
        if(!self.top1){
            self.top1 = num;                
            continue;
        }
        if(!self.top2){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = num;
            continue;
        }
        if(!self.top3){
            self.top3 = num;
            continue;
        }
        if(!self.top4){
            self.top4 = num;
            continue;
        }

      // Adjust our top4 as we fly over the array
        if([self.top1 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = self.top1;
            self.top1 = num;
            continue;
        }
        if([self.top2 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = num;
            continue;

        }
        if([self.top3 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = num;
            continue;

        }
        if([self.top4 intValue] < [num intValue]){
            self.top4 = num;
            continue;

        }

    }

Answer 1

The logic is wrong, but the algorithm is O(n). For every step there's only a constant amount of operations.

The logic error is that when you replace the number in some spot, you need to push the previous values downward, e.g.

   if([self.top1 intValue] < [num intValue]){
        self.top4 = self.top3;
        self.top3 = self.top2;
        self.top2 = self.top1;
        self.top1 = num;
        continue;
    }