Big O Notation for simple loop

Question

I am just starting out in a data structure class, and the instructors have posted 10 problems and asked the Big O of one of them. Based off the posts I have read I am assuming that the Big O of this code would be O(1), since the data parameter is a single data element. However, it does execute multiple times depending on the size of the number so would that make it O(N)?

public class Main {

    public static void main(String[] args) {
        f(100000);
    }

    public static long f (int n) {
        long sum = 0;
        for (long i = 2; i < n; i = i * i) {
            sum += i;
            System.out.println(sum);
        }
        return sum;
    } // end f
}

look at the expression `i = i * i` that should give you a clue. — Red Cricket, Mar 20 '16 at 19:44
[HINT]: Think about what is the effect of squaring the `i` counter is doing to the complexity i.e. how is the number of loop iterations related to `N`. — Luca, Mar 20 '16 at 19:45

score 1 · Accepted Answer · edited May 23 '17 at 10:34

1

This function has a time complexity of O(log(log(n)).

i grows by multiplication in an exponentially growing factor, so that's "double exponential growth" (not sure if that's a valid definition), and the complexity is the inverse. You can read more about this class of complexity here.

edited May 23 '17 at 10:34

Community

1
1

answered Mar 20 '16 at 20:14

Amit

45,440
9
78
110

Thanks for the explanation, and the link. Unfortunately, I don't have enough points to vote the answer as useful. – Vaughnjavier Mar 20 '16 at 21:07
@Vaughnjavier don't worry about it, others can vote if they find this helpful. – Amit Mar 20 '16 at 21:12

dfrib · Answer 2 · 2016-03-20T22:08:51.667

Analyzing your algorithm using Sigma notation

To rigorously analyze the growth of your algorithm, you can use Sigma notation as follows:

with:

where we've also assumed, in the equality using the result from (*), that n is not a number on the form 2^(2^j), for some positive integer j. For values of n where this assumption does not hold, just remove the floor function in the sum over k above.

Result: log-logaritmic time complexity

From the above, it's apparent that your algorithm has a log-logarithmic time complexity, namely (asymptotic upper bound) O(log(log n)).

Big O Notation for simple loop

2 Answers2

Analyzing your algorithm using Sigma notation

Result: log-logaritmic time complexity

Linked