Ninjastic
PostEdited versionsQuotes to this post
Post
Topic
Board Announcements (Altcoins)
Re: NXT :: descendant of Bitcoin - Updated Information
by
Come-from-Beyond
on 14/02/2014, 21:43:52 UTC
Quote from: ChuckOne on February 14, 2014, 09:34:16 PM
Quote from: Come-from-Beyond on February 14, 2014, 09:06:23 PM
Quote from: ChuckOne on February 14, 2014, 08:57:06 PM
Quote from: Come-from-Beyond on February 14, 2014, 08:55:54 PM
Complexity of signing is O(1).

That is plain wrong. The more bits you have to sign the longer signing takes. The question is: how long in terms of the input length.

We would have O(n) if Sign(32_bytes) == Sign(64_bytes) / 2. Actually we have Sign(32_bytes) == Sign(3200_bytes) / 2, so it's more like O(1). Right?

Sorry, still wrong.

It looks more like O(log n) but don't think so, as the whole input has to be read. That still takes O(n).

If we count time to read the input then we should count header processing time too. What about a compromise at O(log log n)? Smiley