Tricky complessità Big-O

Question

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();
    }
}

ho pensato che la complessità sarebbe O (log n).
Ossia come prodotto del ciclo interno, il ciclo esterno -. Verrà mai eseguita più di 100 volte, in modo che possa essere omesso

Quello che non sono sicuro circa è il tempo clausola dovrebbe essere incorporato nella complessità Big-O? Per molto grande i valori che essa potrebbe avere un impatto, o di operazioni aritmetiche, non importa su quale scala, conta come operazioni di base e possono essere omessi?

Answer 1

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

Answer 2

The complexity is O(log m + log n).

The while loop executes log3(m) times - a constant (log3(100)). The outer for loop executes a constant number of times (around 100), and the inner loop executes log2(n) times.

Answer 3

The while loop divides the value of m by a factor of 3, therefore the number of such operations will be log(base 3) m

For the for loops you could think of the number of operations as 2 summations -

summation (k = 0 to i) [ summation (j = 0 to lg n) (1)] summation (k = 0 to i) [lg n + 1] (lg n + 1) ( i + 1) will be total number of operations, of which the log term dominates.

That's why the complexity is O(log (base3) m + lg n) Here the lg refers to log to base 2