Big O complexity of nested loop

kanitov 0
Viewed 13

What could be the big O of this code?

I thought --> n + n/2 + n/3 + .....+1 which is just n, but also looks like O(n^2)

public int sums(int n){
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n/i; j++) {
            sum++;
        }
    }
    return sum;
}
big-o
1 Answers

In general, nested loops fall into the O(n)*O(n) = O(n^2) time complexity order, where one loop takes O(n) and if the function includes loops inside loops, it takes O(n)*O(n) = O(n^2).

Similarly, if the function has ‘m' loops inside the O(n) loop, the order is given by O (n*m), which is referred to as polynomial time complexity function.

jmvcollaborator0
Related