Question

Here are some basic rules for calculating the Big O for some T(n) or an algorithm.

1. Only the highest degree of n matters. For example T(n) = n^3 + 5n^2 + 107 → O(n^3 ) since once n becomes super-massively huge, the other terms just stop mattering.

2. Constant factors don’t matter. T(n) = 500n and T(n) = 0.005n both O(n). Again, as n becomes bigger, these constants stop mattering; what matters is the rate of growth. Example: T(n) = 50n^3 − 2n^2 + 400 → O(n^3 )

3. Counting the number of nested loops usually works.

Please provide your work with the answers.

Answer 1

1. "Only highest degree of n matters."

Only the highest degree of n matters because the lower degree becomes completely dwarfed by the higher degrees of the equations as we consider higher and higher values of n, the contribution of lower degrees becomes dwarfed and irrelevant. Consider the following example for better understanding, in the given equation let's compute the value of T(n) for various values on n like 1,10,100,1000,10000 etc..

For n = 1 : T(1) = 1+5+107 = 113

For n = 10   : T(10) = 1000+500+107 = 1607

For n = 100 : T(100) = 1000000 + 50000 + 107 = 1050107

For n = 1000 : T(1000) = 1000000000 + 5000000 + 107 = 1005000107 = 1.005 X 10

For n = 10¹⁰  : T(10¹⁰) = 10³⁰+ 5 X 10²⁰ + 107 = 10³⁰ approx.

For n = 10²⁰ : T(10²⁰) = 10⁶⁰ + 5 X 10⁴⁰ + 107 = 10⁶⁰ approx.

As it can be observed, the value of T(n) majorly depends only on higher degrees of n. So, it is evident from the above example that as the value n increases the lower order terms stop mattering. Hence, it can be concluded that "Only Highest Degree of n matters."

2. "Constant factors don't matter."

No, the constant factors don't matter in Big-O notation but "yes" they are absolutely relevant while computing computation time of an algorithm. Big-O notation only describes the long term growth rate of functions, rather than their absolute magnitudes. Multiplying a constant only influences its growth by a constant amount, so a function will still follow it's inherent behaviour i.e; a linear function will still grow linearly, a exponential function will still grow exponentially etc.

But these constants are absolutely significant. A function whose runtime is 10¹⁰ⁿ will be way slower than a function whose runtime is just n. The function whose runtime is n³/2 is much faster than one whose runtime is n³. The fact that the first two are both O(n) and the second two are both O(n³) doesn't change the fact that they both won't run in same amount time, since that's not what big-O notation is designed for.

In summary, constant doesn't matter in big-O notation, but they are absolutely significant from the perspective of computation time.

3. "Counting the number of nested loops usually works."

Counting the number of nested loops can give us an idea of complex an algorithm can be but we can not compare two algorithms by counting the no of loops present in them. For better understanding consider the below example,

Code 1 :

int i = n;

while (i > 0)

{

for (int j = 0; j < n; j++)

System.out.println("*");

i = i / 2;

}

Code 2 :

int i = n;

while (i > 0)

{

for (int j = 0; j < n; j++)

System.out.println("*");

i++;

}

In both Code 1 and Code 2 there are two loops, but with just this knowledge we can't comment that both the codes are equally complex. Complexity of the code depends on how the iterator variable is being updated after each iteration.

Code 1 has an complexity of O(n log(n)). The two loops here are nested, but the number of iterations the inner loop runs is independent of the outer loop. Therefore, the total volume of statements can be taken by multiplying both values together. The outer loop iterates O(log n) times. Within EACH iteration, the inner loop iterates n times, independent of the outer loop. Therefore, the time complexity of this code fragment is O(n log n).

Code 2 has an complexity of O(n²).The outer loop iterates O(n) times. Within EACH iteration, the inner loop iterates n times, independent of the outer loop. Therefore, the time complexity of this code fragment is O(n²).

So, even though both the codes have 2 loops but their time complexities are different. Hence, counting the number of nested loops may not work sometimes.