<p>When you’re given an algorithm, what is the best way to derive Big O? It seems like too much brute force to just figure out how many elements are searched and how many calculations are done on them…</p>
<p>Look at the for loops and run an induction on those. (or just multiply them out). Start by getting a pattern and then guess this is the form and then test it out, but you should keep it in terms of n, n+1 etc and not actual numbers. If you are doing a reduction problem (Mergesort, quicksort), look up the Master Theorem. It is usually straight forward, but sometimes you have to do a lot of manipulation.</p>
<p>By the way, if you’re doing this for AP Computer Science (A or AB), don’t worry about it. You probably won’t have to actually determine the Big-O runtime (though you should memorize the runtimes for common algorithms, and know how changes to that algorithm could affect the runtime).</p>
<p>Look at the variable that is changing on successive iterations of the function and/or determines when the function ends. I think it’s pretty obvious which variable this is most of the time. Then try adding one more element or number to that variable and work out a few iterations of the function. How does the number of times it takes to go through the function or the number of calculations required change? For example, if you add one more element to your input and the function takes one more iteration/calculation to complete, you have a O(n) function. </p>
<p>This is the easiest way I know of, although I think I explained it in a really unintuitive way.</p>
<p>This is basically what Senritsu said, but I’ll include examples.</p>
<p>Big-Oh usually isn’t that bad, at least for the basic stuff you’ll see on the AP, because it’s order-of-magnitude, not exact number of calculations.</p>
<p>so </p>
<p>for (i=0;i< N; i++)
//SOP(blah)</p>
<p>and </p>
<p>for(i=0;i<N;i++)
//do blah</p>
<p>for(i=0;i<N;i++)
//do blah2</p>
<p>will both be O(n), even though in practice one does n operations and one 2n.</p>
<p>In general, look for loops, the upper bound of the counter that controls those loops, and with recursion and sorts also things like dividing collections into two (logn), etc.</p>
<p>Basically you just have to get a general sense of the operations going on, not get into nitpicky details.</p>