[Solved] Big O Of Mod 20

Question

Assuming that you can insert integers of any size, the complexity will be the same as the complexity of division.

So it is O(log n) due to log n is the number of digits.

Notice 1: If you can only insert 32 or 64 bit integers, the “complexity” will be O(1).

Notice 2: Since computers save all numbers in binary, you can get n % 2^k in konstant time, even if n can be of any size. You just take the k smalest bits. This dont work for n % 20 without computing the representation of n to the base 20.

If you want to know what Big-O means, this post will help you.

Accepted Answer

Assuming that you can insert integers of any size, the complexity will be the same as the complexity of division.

So it is O(log n) due to log n is the number of digits.

Notice 1: If you can only insert 32 or 64 bit integers, the “complexity” will be O(1).

Notice 2: Since computers save all numbers in binary, you can get n % 2^k in konstant time, even if n can be of any size. You just take the k smalest bits. This dont work for n % 20 without computing the representation of n to the base 20.

If you want to know what Big-O means, this post will help you.