I understand that a sequence of statements and conditional checks are o(1) a loo
ID: 3547849 • 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; // O(1)
for (int a = 0; a < N; a++) // O(1) ; 0(n) ; O(n)
{
something += a; // O(n)
}
for (int b = 0; b < N; b++) // O(1) ; 0(n) ; O(n)
{
something *= b; // O(n)
for (int c = b; c < N; c++) // O(n) ; O(n^2) ; O(n^2)
{
something -= c; //O(n^2)
if (flag) // O(n^2)
{
for (int d = c; d < N; d++) // O(n^2) ; 0(n^3) ; O(n^3)
{
something /= 2; //O(n^3)
}
}
}
}
return something; O(n^3)
}
However, here are my options
N^3
N(N + 1)(N + 2)(N + 3)/24
O(N(N + 1)/2) N(N + 1)/2 + 1 N(N + 1)(N + 2)/6 + N
O(N(N + 1)(N + 2)/6
N^2
O(N + 1)
O(N(N + 1)(N + 2)/6 + N(N + 1)/2) N(N - 1)/2
O(1)
O(N)
O(N(N + 1)/2 + N)
Explanation / Answer
The answer is O(N^3) as There are three for loops one inside other
Though there is for loop outside which is O(N) but O(N+N^3) is equal to O(N^3)
The first for loop is O(N)
Each conditional statements and Statements are O(1)