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 have read, this code should be O((n^3)/4). But apparently its not. to find the Big-O for nested loops are you supposed to multiply the bounds? So this one should be num *n *n or n/4 *n *n.
O((n^3)/4) makes no sense in terms of big-O notation since it's meant to measure the complexity as a ratio of the argument. Dividing by 4 has no effect since that changes the value of the ratio but not its nature.
All of these are equivalent:
O(n^3)
O(n^3/4)
O(n^3*1e6)
Other terms only make sense when they include an n term, such as:
O(n^3 / log(n))
O(n^3 * 10^n)
As Anthony Kanago rightly points out, it's convention to:
O(n^2+n) = O(n^2).O(n^2/4) = O(n^2).As an aside, I don't agree with that first rule since I believe O(n^4+n^3+n^2+n) is markedly worse than just O(n^4). I believe any term that depends on the input parameter should be included.
The outer loop is N. The second loop is N/4, and is executed N times, giving N^2/4, or O(N^2).
The last loop is N/4, and is executed N^2/4 times, giving N^3/4.
However, in big-O, it's just O(N^3).
From http://en.wikipedia.org/wiki/Big_O_notation you can see that constants like the 1/4 do not play a role for determining the Big-O notation. The only interesting fact is that it is n^3, thus O(N^3).
A small technicality. Big O notation is intended to describe complexity in terms of the 'size' of the input, not the numeric value. If your input is a number, then the size of the input is the number of digits of your number. Alas, your algorithm is O(2^N^3) with N being the number of digits.