Confusion about an answer on SO

[adam2016]

Hey guys,

so I'm reading this post on SO - https://stackoverflow.com/questions/9152890/what-would-cause-an-algorithm-to-have-olog-n-complexity

it is the first answer and it's under processing values one digit at a time,

the poster says

How many digits are in the base-10 number n? Well, if there are k digits in the number, then we'd have that the biggest digit is some multiple of 10k. The largest k-digit number is 999...9, k times, and this is equal to 10k + 1 - 1. Consequently, if we know that n has k digits in it, then we know that the value of n is at most 10k + 1 - 1. If we want to solve for k in terms of n, we get

n ≤ 10k+1 - 1

n + 1 ≤ 10k+1

log10 (n + 1) ≤ k + 1

(log10 (n + 1)) - 1 ≤ k

From which we get that k is approximately the base-10 logarithm of n. In other words, the number of digits in n is O(log n).

but I did this on a piece of paper and this didn't seem to be quite right, so let's say N has 3 digits, N <= 10^3+1 - 1

in other words N has to be smaller than (10^3+1)-1, but (10^4) - 1 is 9999, this is 4 digits??

but when I do log(1000)-1 I do indeed get 3, so how come I get the right answer when I use log(N+1) and again (10^4) is 9999 way past the max number?

or maybe I'm misunderstanding what the poster is trying to explain?

thanks

[marhuum]

Imho the OP might slip with extra + 1 , so correct is n <= ( 10^k ) - 1
just k insead of (k+1)
but he's a great pedagogical teacher

[helios]

The base x representation of n has exactly floor(log_x(n) + 1) digits.

[adam2016]

@helios

I came across the post on reddit relating to the same question, where the poster says

10^k is a one followed by k zeros. That is the smallest number with k+1 digits,

Thus, the k-digit numbers are precisely those in the half-open interval [10^(k-1), 10^k )

For all of these numbers their base-10 logarithm is in [k-1,k), and thus the floor of the base-10 logarithm is k-1.

Hence, the exact formula that gives you the number of digits in any positive integer n is 1+floor(log10(n))

the last point matches with your post with that the number of digits will be floor(logx(n) + 1) post

to be honest I have no idea what the poster is saying :/


also going back to the SO post the poster mentions

How many digits are in the base-10 number n? Well, if there are k digits in the number, then we'd have that the biggest digit is some multiple of 10k. The largest k-digit number is 999...9, k times, and this is equal to (10^k + 1) - 1. Consequently, if we know that n has k digits in it, then we know that the value of n is at most (10^k + 1) - 1. If we want to solve for k in terms of n, we get

so lets take a 3 digit number n, k = 2 , from what I have read k is 2 as 0 is counted, so n is at least 10^2

ok great, but what is meant by " Well, if there are k digits in the number, then we'd have that the biggest digit is some multiple of 10k"

and on a side note, why is k = 2? I know we start counting at 0, but it kind of sounds strange when he says that n is a k digit number and it has k digits, but if n has k digits ( 2 in this case ) wouldn't this be a number like 99? 999 has 3 digits but k = 2?

Well, if there are k digits in the number, then we'd have that the biggest digit is some multiple of 10k

thanks

[helios]

Please, if you're going to quote a text with formatted exponents have the decency to add the relevant ^ symbols, otherwise it's ambiguous.

so lets take a 3 digit number n, k = 2

Why? Read the text you quoted.
"if there are k digits in the number". That means k being the number of digits in the representation is a basic assumption.

Let S be a base k representation of natural n, of length l. That means that these three statements must be true:
* for all i in [0; l), S[i] in [0; k)
* n = S[l - 1] * k^(l - 1) + ... + S[0] * k^0
* S[l - 1] > 0
It's also true that, with these constraints, the largest possible value of n is that where all positions of S are equal to k - 1, and also that n is strictly less than k^l (this is more difficult to prove in these general terms, but obvious for the typical case of k=10, so I don't think it's necessary). Since S[l - 1] > 0, necessarily n >= k^(l - 1), since that's the smallest number that's representable in l k base digits.
So now we know that k^(l - 1) <= n < k^l. It follows that
l - 1 <= log_k(n) < l
But what we want to find out is l, so:
l <= log_k(n) + 1 < l + 1
In other words, log_k(n) + 1 is a number that's either exactly equal to the number digits necessary to represent n in base k (l), or is less than one above that value. So, if you calculate log_k(n) + 1 and always ignore the fractional part, the result should always be l. Or, in other words, l = floor(log_k(n) + 1).

[adam2016]

I thought I did, must have forgot one or two of them

Why? Read the text you quoted.
"if there are k digits in the number". That means k being the number of digits in the representation is a basic assumption.

but there is 3 digits in the number?? yet we say k = 2??

[helios]

Who said k = 2? You did. The value of k is what you're trying to find out. Why are you starting from the assumption that its value is 2?

[adam2016]

well there is 3 digits so k should = 3?

but if we plugged 3 into the below equations

n ≤ (10^k+1) - 1

n + 1 ≤ 10^k+1

we would get

n ≤ (10^3+1) - 1

n + 1 ≤ 10^3+1

so lets say again we have a 3 digit number, the max number would be (10^3+1)-1 = 10000 - 1 = 9999 - but this is wrong because this is 4 digits?

[helios]

Please use parentheses properly. 10^3+1 != 10^(3+1)

It is an error. If n is a k digit number in base b, then n < b^k.

[adam2016]

so it isn't 10^(k+1) rather 10^(k) ?

[helios]

Both
n < 10^k
and
n < 10^(k + 1)
are true, but 10^k is the closer bound. 10^k - 1 is a k-digit number; 10^(k +1) - 1 is not.

[adam2016]

that makes sense, I'm surprised nobody pointed out the mistake on the post, it's got 285 upvotes :/

I wonder how he made the mistake of k+1 instead of k so many times

[helios]

It's not really a mistake. The final conclusion is true and follows from the reasoning, it just doesn't answer the question you were asking. (log10 (n + 1)) - 1 ≤ k just gives you a lower bound for the number of decimal digits of n, which is useful to get some idea about the growth of the function, but it doesn't tell you how to actually calculate k. To do that you need to bound k as closely as possible, like I did above.

[adam2016]

Thanks Helios, to be honest reading books on algorithms and even looking at tutorials online, I always seem to have a problem with the reasoning behind the design of algorithms ie the math behind the algorithms complexity and design.

I have no problem implementing and understanding the code but when an author tries to explain mathematical notation with algorithms I completely zone out.

Do you know any good resources to help give me some understanding on how to read this notation, I have searched on google but can't find any and when I do they dive straight into the deep end, I'm looking for kind of like an introductory guide that can help me.

I know it's discrete mathematics but is there certain specific topics that I should learn to help me understand the notations? ( and I'm talking about more than just time complexity and space complexity ) I'm talking in general, for example most of the notation you used here and others use when describing efficiency etc of algorithms just looks alien to me.

thanks! :)

[helios]

The notation isn't really important. Notice for example that in the previous argument I used "in" instead of ∈ because I didn't want to go look for the symbol. Every piece of notation can be replaced by English words or phrases and the argument should still make sense, it would just be very verbose. If you struggle with this sort of thing, it's probably because you haven't been exposed to enough formal proofs. I'd recommend a university-level course on calculus with an emphasis on proofs.

For example, can you prove this?

Let k be a natural greater than 1 and n be a non-negative integer, then
k^n = (k - 1) * k^(n - 1) + (k - 1) * k^(n - 2) + ... + (k - 1) * k^0 + 1