CODEWITHSUNDEEP
javabig-ocomputer-science
Nemo_Sol
Nemo_Sol

Reputation: 352

Big O Complexity for nested loop

for (i = 0; i < 2*n; i += 2) 
{
  for (j=n; j > i; j--)
    //some code that yields O(1)
}

I thought the above would yield n*log(n) but I've seen another source say that it is really is n^2 complexity for big Oh. Please explain to me which it is and how i could approach problems like this in the future.

Upvotes: 2

Views: 103

Answers (2)

flogram_dev
flogram_dev

Reputation: 42868

You have a loop that depends on n and inside that loop you have another loop that also depends on n, thus the resulting O is O(n*n) i.e. O(n^2).

Big O only provides an upper bound on the growth rate of an algorithm. Thus all constant factors are discarded.

Upvotes: 5

Failed Scientist
Failed Scientist

Reputation: 2027

Since Big O is for Upper Bound, so N * N will always be <= N^2, resulting in O(N*2). Answer is right

Upvotes: 1

Related Questions