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

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is the complexity of this algorithm? I thought it was big O(n) - using only 1 for...in loop
    text
    copied!<p><strong>ios project</strong> <a href="https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates" rel="nofollow">https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates</a></p> <p>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). </p> <pre><code>// 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] &lt; [num intValue]){ self.top1 = num; continue; } if([self.top2 intValue] &lt; [num intValue]){ self.top2 = num; continue; } if([self.top3 intValue] &lt; [num intValue]){ self.top3 = num; continue; } if([self.top4 intValue] &lt; [num intValue]){ self.top4 = num; continue; } } </code></pre> <p><strong>Update</strong> 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.</p> <pre><code>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] &lt; [num intValue]){ self.top4 = self.top3; self.top3 = self.top2; self.top2 = self.top1; self.top1 = num; continue; } if([self.top2 intValue] &lt; [num intValue]){ self.top4 = self.top3; self.top3 = self.top2; self.top2 = num; continue; } if([self.top3 intValue] &lt; [num intValue]){ self.top4 = self.top3; self.top3 = num; continue; } if([self.top4 intValue] &lt; [num intValue]){ self.top4 = num; continue; } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload