Newbie questions

Richard A. O'Keefe ok@REDACTED
Fri Mar 31 01:08:43 CEST 2006


Raimo Niskanen <raimo@REDACTED> wrote:
	Regarding your problem about determining the number of decimal
	digits in a number, I just came to think of a simple enough
	brute force O(log(N)) or rather O(NN) where NN is the
	number of digits in the number:
	
	    digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).
	
	    digits(N, M, D) when M > N -> D;
	    digits(N, M, D) -> digits(N, M*10, D+1).
	
I am reading "O(NN)" as "O(#Digits)".
Unfortunately, this is O(#Digits**2), because the multiplication M*10
is O(#Digits), not O(1).




More information about the erlang-questions mailing list