Big-O notation

Basics of time complexity analysis. Sources: good clear article, video on how to calculate time complexity

15 flashcards · Computer Science · by Xiang J

f(n) = O(g(n)) Given f(n) = 6n + 4, what is g(n)?
Let's guess that g(n) = n. Let's see if it satisfies our definition: lim(n->∞) (6n + 4)/n lim(n->∞) 6 + 4/n 6 and 6 < ∞, therefore we guessed it right.
Simple programs can be analyzed by counting the nested loops of the program.
A single loop over n items yields O(n). (loop in loop) yields O(n^2). (loop in loop in loop) yields O(n^3). If loops are sequential, the slowest of them determines the asymptotic behavior of the program: (loop in loop) + 3 loops yields O(n^2).
What is the rule of thumb for calculating big-O of some function?
To calculate big-O notation: identify formula for algorithm complexity. Let's say for example two loops with another one nested inside, then another three loops not nested: 2N² + 3N remove anything except the highest-order term: 2N² remove all constants: N²
O(n^2) may actually run faster that O(n) for smaller ns.
Big O notations only tells us how algorithm behaves under large n.
2n + 2 = O(n^666) is technically true according to rigorous definition.
But it's not a very useful knowledge, so usually we are asked to calculate a tight upper bound (O(n) in this case).
f(n) = O(g(n)) In the context of computer science, - what is n and f(n)?
n is input length, f(n) is amount of instructions that will need to be executed for the given input length in the worst-case scenario.
Why is Big O notation called so?
The letter O is used because the growth rate of a function is also referred to as order of the function.
What is a worst-case scenario of this procedure: 1 let max = array[0]; 2 3 for (let i = 0; i < n; ++i) { 4 if (array[i] >= max) { 5 max = array[i]; 6 } 7 }
When line 5 executes.
f(n) = O(g(n)) What is a time complexity here?
g(n) function.
f is bounded above by g (up to constant factor) asymptotically
f is bounded both above and below by g asymptotically
f is bounded below by g asymptotically
f is dominated by g asymptotically
f is equal to g asymptotically
f dominates g asymptotically