Analysis of Algorithms Question

[sydney25]

I'm having trouble with the following question:

The analysis of algorithms for large integers is not affected by the choice of a measure for the size of operands: the number of computer words needed, or the length of their representation in decimal or binary will do equally well. Show that this remark would in fact be false were we considering exponential time.

Could someone tell me if I'm on the right track with the following answer:

Let’s say a problem has 5^n numbers. Every time you add 1 to n your answer grows by 5 times. As an example, if n is 8, then 58 = 390,625. Represented in binary your answer is 1011111010111100001. It requires 3 to 4 times the bits to represent the binary than a decimal representation.

I understand that binary representation is much larger than decimal representation. How do I explain this considering exponential time?

Any help would be appreciated.

 

[Denis]

I'm having trouble with the following question:
The analysis of algorithms for large integers is not affected by the choice of a measure for the size of operands: the number of computer words needed, or the length of their representation in decimal or binary will do equally well. Show that this remark would in fact be false were we considering exponential time.
Could someone tell me if I'm on the right track with the following answer:
Let’s say a problem has 5^n numbers. Every time you add 1 to n your answer grows by 5 times. As an example, if n is 8, then 58 = 390,625. Represented in binary your answer is 1011111010111100001. It requires 3 to 4 times the bits to represent the binary than a decimal representation.
I understand that binary representation is much larger than decimal representation. How do I explain this considering exponential time?
Any help would be appreciated.

Not sure what you're asking, but looks like to me you need to set
your decimal = 2^m, m being the number of binary bits;
5^n = ceiling(2^m)

2^m = 5^n
m = log(5^n) / log(2)

m = log(390625) / log(2) = 18.57~ ; ceiling = 19, which is the bits in 1011111010111100001.

Not sure what the "GURUtical" way to handle the "ceiling" is...
m = ABS[log(5^n) / log(2)] + 1 ????

I guess you'd use d^n instead of 5^n, to make it "general".

 

[sydney25]

Thanks for the help.

What is confusing me is the "Show that this remark would in fact be false were we considering exponential time." part of the problem

 

[Denis]

Thanks for the help.
What is confusing me is the "Show that this remark would in fact be false were we considering exponential time." part of the problem

It's not confusing ONLY to you
Did you try a http://www.google.com search on exponential time?

 

[sydney25]

That's funny. I can never get enough of that Canadian sense of humor. Thanks for helping me out - or should I say, "oot."