Question

Using C++ please explain

What is the Big-O time complexity of the following code: for (int i=0; i<N; i+=2) { ... constant time operations... Select one: o a. O(n^2) O b. O(log n) c. O(n) O d. 0(1)

Answer 1

for(int i=0;i<N;i+=2)
{
//constant time operations

}
Big O complexity :O(N)
explanation:
since i is incremented by 2, in each iteration
the loop run for N/2
which makes complexity :O(N/2)

for(int i=1;i<N;i*=2)
{
//constant time operations

}
Big O complexity :O(logN)
explanation:
since i is doubled, in each iteration
the loop run for logN times
which makes complexity :O(logN)


int x=10;
for(int i=1;i<N;i*=2)
{
for(int j=0;j<N;j+=2)
{
x++;
}
}
Big O complexity :O(NLogN)
explanation:
outer loop runs for LogN times
inner loop runs for N/2 times for each iteration of outer loop
overall complexity : LogN * N/2 = O(NlogN)