2 
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.

Improve this question
2
  • 2
    It might help to know that the sum of integers from 1 to n is equal to n*(n+1)/2, which is clearly O(n^2). Commented Mar 17, 2015 at 1:30
  • its o(n^2), total cycles would need to reduce by a multiplicative factor, say 1/2, each iteration for it to be o(n log n). Commented Mar 17, 2015 at 1:41

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This. Discarding constant factors is a much better way to explain it.
1

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

Improve this answer

5 Comments

Since the increment is not 1 in the outer loop, this is not true since there are not N steps but rather N/2
Check the outer loop again. 2N in steps of 2 will equate to?
Oh, i missed that. Thanks. however, if it was just i<n would it be n log n?
Still it would be N^2 as Big O as I mentioned in my answer represents UPPER BOUND of the function
Dividing the number of steps by 2 (or any constant factor) still gives you the same Big O.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.