Big-O Challenges

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

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

What I'm not sure is the while clause, should it be included in Big-O complexity? For very large values, can this affect me or arithmetic operations, it doesn’t matter on what scale, can it be considered basic operations and can be omitted?

Answer 1

The while is O(log m) , because you keep dividing m by 3 until it is lower 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 you exceed n .

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

or arithmetic operations, it does not matter on what scale, considered basic operations and can be omitted?

Arithmetic operations can usually be omitted, yes. However, it also depends on the language. This is similar to Java, and it looks like you are using primitive types. In this case, it is normal to consider arithmetic operations O(1) , yes. But if you use, for example, large integers, this is not entirely normal, since addition and multiplication are no longer O(1) .

Answer 2

Complexity 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 (about 100), and the inner loop executes log2 (n) times.

Answer 3

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

For for loops, you can represent the number of operations as 2 sums -

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

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