Looking for Big-O with multiple nested loops?

Question

int num = n/4; for (int i = 1; i <= num; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { int count = 1; } } } 

According to the books I read, this code should be O ((n ^ 3) / 4). But apparently he is not. to find Big-O for nested loops, do you have to multiply the boundaries? So it should be num * n * n or n / 4 * n * n.

Answer 1

O((n^3)/4) does not make sense in terms of the notation of large O, since it is designed to measure complexity as a ratio of an argument. The division into 4 does not affect, because it changes the value of the relationship, but not its nature.

All of them are equivalent:

 O(n^3) O(n^3/4) O(n^3*1e6) 

Other terms make sense only when they include the term n , for example:

 O(n^3 / log(n)) O(n^3 * 10^n) 

As Anthony Kanaga correctly points out, this agreement:

• supports only the term with the highest growth rate for the sums: O(n^2+n) = O(n^2) .
• get rid of constants for products: O(n^2/4) = O(n^2) .

As an aside, I do not always agree with this first rule in all cases. This is a good rule to determine the maximum growth rate of a function, but for things like comparing algorithms ^(a) where you can reasonably set a limit on the input parameter, something like O(n^4+n^3+n^2+n) noticeably worse than just O(n^4) .

In this case, any expression that depends on the input parameter should be included. In fact, even constant terms may be useful there. Compare, for example, O(n+1e100) with O(n^2) - the latter will exceed the former for a rather long time, until n becomes large enough to affect the constant term.

---

^(a) There are, of course, those who would say that this should not be used in this way, but pragmatism often overcomes dogmatism in the real world :-)

Answer 2

From http://en.wikipedia.org/wiki/Big_O_notation you can see that constants like 1/4 do not play a role in defining Big-O notation. The only interesting fact is that it is n ^ 3, therefore O (N ^ 3).

Answer 3

Formally, the time complexity can be derived as follows:

Answer 4

Little technical significance. Big O notation is intended to describe complexity in terms of the "size" of an input, not a numerical value. If your input is a number, then the input size is the number of digits of your number. Alas, your algorithm is O (2 ^ N ^ 3), where N is the number of digits.

More on this topic