Calculate big O

Question

So I want to calculate the Big O for this snippet of code, but I am unsure of how to approach it. Some help to get started would be appreciated.

`

            for ( i = 1 ; i * i < n ; i++){
                for ( j = 1 ; j < n ; j++)
                {
                  ...
                }
            }
            for ( i = 1 ; i < n ; i++){
                for ( j = i % 5 ; i + j < 2000; j++)
                {
                  ...
                }

`

Here's a massive post regarding Big O notation: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it — valverij, Apr 10 '13 at 16:12
First inner loop is O(n), outer loop O(sqrt(n)), which means O(n*log n). Second loop... I'll have to say O(n) since when n goes to infinity, the inner loop goes to constant, but it's been a while since I took math, so take it with a grain of salt ;) — Joachim Isaksson, Apr 10 '13 at 16:20

score 2 · Accepted Answer · edited Aug 03 '13 at 10:49

2

Alright, so we start at the first inner loop, and see that it is O(n). Then, i goes from 1 to square root n, so the complexity for that loop is O(sqrt(n)). We then multiply them to find the complexity for the first nested loop, which is O(n * sqrt(n)).

The second outer loop has complexity n, and the inner loop runs a defined number of times (not dependent on n), so the total complexity is O(n * sqrt(n) + n).

edited Aug 03 '13 at 10:49

taskinoor

45,586
12
116
142

answered Apr 10 '13 at 16:11

James

2,635
5
23
30

To note then, `O(n*sqrt(n)+n)` is the same as `O(n*log(n))`. – Joachim Isaksson Apr 10 '13 at 16:55

score 0 · Answer 2 · answered Apr 10 '13 at 16:10

Big O is the worst case scenario and in this case is N^2 because you have a nested for loop inside of the first for loop.

The second set of for loops is only big O of N because the inner for loop will run at most of 2000 times and that in the scope of things is very minor, especially when N is huge.

Calculate big O

2 Answers2