I understand that a sequence of statements and conditional checks are o(1) a loo
ID: 3547285 • Letter: I
Question
I understand that a sequence of statements and conditional checks are o(1)
a loop is 0(n) where n is the number of loop executions
nested loops are o(n^2) where n is number of times inner loop executes
n is euqual to 10 and flag is equal to true.
I have a program that I am trying to determine the big oh values on.
The red is what I need to figure out step by step.
public long getSomething(long N, boolean flag)
{
long something = 0; 0(1)
for (int a = 0; a < N; a++) int a =0 is 0(1), a<N=0(n) and a++=0(n)
{
something += a; 0(n)
}
for (int b = 0; b < N; b++) int b=0 is 0(1),b<N=0(n), b++=0(n)
{
something *= b; 0(n)
for (int c = b; c < N; c++) int c=b 0(n^2), c<N N(n+1) c++
{
something -= c;
if (flag)
{
for (int d = c; d < N; d++)
{
something /= 2;
}
}
}
}
return something;
}
Explanation / Answer
public long getSomething(long N, boolean flag)
{
long something = 0; // O(1)
for (int a = 0; a < N; a++) // O(1) ; 0(n) ; O(n)
{
something += a; // n * 0(1) => O(n)
}
for (int b = 0; b < N; b++) // O(1) ; 0(n) ; O(n)
{
something *= b; // n * 0(1) => O(n)
for (int c = b; c < N; c++) // n * (O(1) ; 0(n) ; O(n)) => O(n) ; O(n^2) ; O(n^2)
{
something -= c; // n^2 * O(1) => O(n^2)
if (flag) // n^2 * O(1) => O(n^2)
{
for (int d = c; d < N; d++) // n^2 * (O(1) ; 0(n) ; O(n)) => O(n^2) ; 0(n^3) ; O(n^3)
{
something /= 2; // n^3 * O(1) => O(n^3)
}
}
}
}
return something;
}
The above is the same code with the final Big O values for each of the lines representing the operation.
The best way of finding the big O value is to find its individual Big O value and multiply it the number of times it occurs.
Thus,
operations cost => O(1)
operations in a loop => n*O(1) => O(n)
operations in a loop inside another loop (nested loops) => n2*O(1) => O(n^2)
and so on.
And in a process if a there are many sub processes with different Big O values, then the final Big O value is the one with the biggest big O value.
Thus, the big O value of the whole function getSomething is O(n^3) since it is the biggest of all the others.
Hope I solved your doubts, If you have any more queries, just comment and I can help you.