In the definition of Bigo why is the for N J no needed 2 If

In the definition of Big-o, why is the \"for N >J no\" needed? 2. If f 1 (N) 2N and f2 (N) 3N, why are they both o (N), since 3N is larger than 2N for N> 12 3. If a function is known to be o (N), what would you expect to happen to the running time if the input size is doubled? What if the function was o (N*N) Explain your answer

Solution

Big O notation is the language we use for articulating how long an algorithm takes to run. It\'s how we compare the efficiency of different approaches to a problem.

With big O notation we express the runtime in terms of—brace yourself—how quickly it grows relative to the input, as the input gets arbitrarily large.

Let\'s break that down:

how quickly the runtime grows—Some external factors affect the time it takes for a function to run: the speed of the processor, what else the computer is running, etc. So it\'s hard to make strong statements about the exact runtime of an algorithm. Instead we use big O notation to express how quickly its runtime grows.
relative to the input—Since we\'re not looking at an exact number, we need something to phrase our runtime growth in terms of. We use the size of the input. So we can say things like the runtime grows \"on the order of the size of the input\" (O(n)O(n)) or \"on the order of the square of the size of the input\" (O(n^2)O(n2))