Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?

Thanks in advance,
KP Bhat

[ Post a follow-up to this message ]

Generic Usenet Account wrote:
quote:

> (1) What is the time-complexity of the base64 encoding/decoding
> process?


O(n)
quote:

> (2) On an average, what is the size of the encoded data in relation to
> the original (i.e. binary) data?


Encoded data is a 35% increase over the original data.

Regards
Stuart

[ Post a follow-up to this message ]

On Fri, 12 Sep 2003, Generic Usenet Account wrote:
quote:

> Could someone kindly answer the following two questions I have
> regarding base64 encoding:
> (1) What is the time-complexity of the base64 encoding/decoding
> process?
> (2) On an average, what is the size of the encoded data in relation to
> the original (i.e. binary) data?


Ah, September.  The start of a new school year.

The answer to question (1) is that it depends upon the processor chip.  A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.

The answer to question (2) is that the size of the encoded data is
inversely proportional to the original data due to the patented
compression mechanism used by BASE64.

If you don't believe these answers, then read RFC 2045 where BASE64 is
specified and the answers to your question become obvious.  Otherwise,
just submit the answers as-is on your homework, and you'll get the grade
that you deserve.

-- Mark --

http://staff.washington.edu/mrc
Science does not emerge from voting, party politics, or public debate.
Si vis pacem, para bellum.

[ Post a follow-up to this message ]

"Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu...
quote:

> On Fri, 12 Sep 2003, Generic Usenet Account wrote: 
>
> Ah, September.  The start of a new school year.
>
> The answer to question (1) is that it depends upon the processor chip.  A
> 64 bit chip will handle the data four times as fast; twice between the
> entire data fits, and twice because of the efficiency of not having to
> split the data.


No, time complexity does not depend on processor chip. The answer is still
O(n). You can manipulate the constants with a different processor, but the
asymptotic time complexity is not affected. The relationship is linear.
--
Dale King

[ Post a follow-up to this message ]

>>>>> "Mark" == Mark Crispin <mrc@CAC.Washington.EDU> writes:

Mark> Ah, September.  The start of a new school year.

Now now. You *know* it's been September since 1992.

--lyndon

[ Post a follow-up to this message ]

In comp.compression Dale King <KingD@tmicha.net> wrote:
quote:

> "Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
> news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu... 
>
> No, time complexity does not depend on processor chip. The answer is still
> O(n). You can manipulate the constants with a different processor, but the
> asymptotic time complexity is not affected. The relationship is linear.


Before you correct him, go back and read what he wrote again.
Carefully.  The entire post.  Then ask yourself "How was he answering
the question?" and see if the answer is appropriate.

--

That's News To Me!
newstome@comcast.net

[ Post a follow-up to this message ]

Stuart Caie <kyzer@4u.net> wrote in message news:<3f62082e$0$261$cc9e4d1f@news.dial.pipex.com>...[
QUOTE]
> Generic Usenet Account wrote: 
>
> O(n)
> 
>
> Encoded data is a 35% increase over the original data.
>
> Regards
> Stuart[/QUOTE]

Thanks to everyone who responded.

I wonder what the "increase factor" is for other binary to text
encoding schemes like UUEncode, XXEncode, Binhex, Quoted-Printable etc
(list gleaned from http://www.xceedsoft.com/products/binEncod/index.htm).
Also, is there any other prominent binary to text encoding scheme
that I left out?

Regards,
KP Bhat

[ Post a follow-up to this message ]

o Generic Usenet Account <usenet@sta.samsung.com>:
quote:

> I wonder what the "increase factor" is for other binary to text
> encoding schemes like UUEncode, XXEncode, Binhex, Quoted-Printable etc
> (list gleaned from http://www.xceedsoft.com/products/binEncod/index.htm).


I wonder why people don't use google for looking up the web.  In
less than 4mins I found
http://www.fpx.de/fp/Software/UUDev...troduction.html
in the uudeview homepage.  You will find there a brief
description for these formats.  uuencode, xxencode, BinHex are
``three in four'' encodings like base64. So increase factor is
about the same.

QP is completely different. Each non-ascii character will (ascii
chars may) be encoded to their hex-representation (i.e. `=FC'
for the german u-umlaut, `ü'). Depending on input data, there
is an increase of encoded data beetween 0% and 200%.

A rule when to use base64 or quoted-printable has been discussed
here before.

For details on base64 or QP read rfc2045, like Mark told you.
quote:

> Also, is there any other prominent binary to text encoding scheme
> that I left out?


yEnc.  Different story.

flori

[ Post a follow-up to this message ]

<newstome@comcast.net> wrote in message
news:yHq8b.424393$YN5.285929@sccrnsc01...
quote:

> In comp.compression Dale King <KingD@tmicha.net> wrote: 
to[QUOTE] 
A[QUOTE] 
still[QUOTE] 
the[QUOTE] 
>
> Before you correct him, go back and read what he wrote again.
> Carefully.  The entire post.  Then ask yourself "How was he answering
> the question?" and see if the answer is appropriate.


I read it again and my answer is still unchanged. Time complexity does not
depend on the processor chip. The execution time may be sped up with a
different processor, but the asymptotic time complexity does not change.
Time complexity does not measure absolute execution time, but the
relationship of execution time to input size.

--
Dale King

[ Post a follow-up to this message ]

[Dale King]:
quote:

>
>   <newstome@comcast.net> wrote: 
>
>   I read it again and my answer is still unchanged.


then you are as dense as Mark Crispin secretly hoped the student would
be.

--
Kjetil T.			|  read and make up your own mind
|  http://www.cactus48.com/truth.html

[ Post a follow-up to this message ]