Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tricky Big-O complexity

public void foo(int n, int m) {
    int i = m;

    while (i > 100) {
        i = i / 3;
    }
    for (int k = i ; k >= 0; k--) {
        for (int j = 1; j < n; j *= 2) {
            System.out.print(k + "\t" + j);
        }
        System.out.println();
    }
}

I figured the complexity would be O(logn).
That is as a product of the inner loop, the outer loop -- will never be executed more than 100 times, so it can be omitted.

What I'm not sure about is the while clause, should it be incorporated into the Big-O complexity? For very large i values it could make an impact, or arithmetic operations, doesn't matter on what scale, count as basic operations and can be omitted?

like image 680
George Kagan Avatar asked Jun 06 '10 12:06

George Kagan


People also ask

What is the complexity of big O?

Big O Notation is a way to measure an algorithm's efficiency. It measures the time it takes to run your function as the input grows. Or in other words, how well does the function scale. There are two parts to measuring efficiency — time complexity and space complexity.

Is big O for the worst time?

Worst case — represented as Big O Notation or O(n)Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. It provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm.

Is Big O notation difficult?

Big O can get very complex, and it can be hard to conceptualize. The few things I was able to learn so far are really just the tip of the iceberg. However, once you understand why and how it works, it's easier to understand some of the more complex ideas.

Which Big O notation is fastest?

The fastest possible running time for any algorithm is O(1), commonly referred to as Constant Running Time. In this case, the algorithm always takes the same amount of time to execute, regardless of the input size.


1 Answers

The while loop is O(log m) because you keep dividing m by 3 until it is below or equal to 100.

Since 100 is a constant in your case, it can be ignored, yes.

The inner loop is O(log n) as you said, because you multiply j by 2 until it exceeds n.

Therefore the total complexity is O(log n + log m).

or arithmetic operations, doesn't matter on what scale, count as basic operations and can be omitted?

Arithmetic operations can usually be omitted, yes. However, it also depends on the language. This looks like Java and it looks like you're using primitive types. In this case it's ok to consider arithmetic operations O(1), yes. But if you use big integers for example, that's not really ok anymore, as addition and multiplication are no longer O(1).

like image 200
IVlad Avatar answered Oct 01 '22 01:10

IVlad