1

I've made a data structure that has insert, search, and delete functions that are base on the number of characters in the key.

As an example if it's a number based key (base10), then the complexity for the given functions is at worst equal to the number of digits in the key. If was the case how would I express that?

I did some reading and I came up with this. O(log10⟨N⟩) Is this right?

| improve this question | |
2

Normally, if the constraint we're interested in is the length of the number in bits rather than the value of the number or the size/length of some data structure, we simply define N to be the length of the number and express big-O in terms of that. So I would say that your operations are O(n) or linear time and be sure to mention somewhere that n is the length of the key as opposed to the value of the key or the number of nodes already inserted or whatever.

This is most often done in the context of integer factorization. Whenever someone tells you that we have yet to find a polynomial-time algorithm for finding the prime factorization of an integer, they're talking about time complexity where N is defined as the length of the integer. If you instead define N as the value of the integer, the obvious brute force algorithm of simply trying all possible factors is obviously a polynomial time solution. This is sometimes called pseudo-polynomial time. So I suppose you could say your operations run in "pseudo-logarithmic time" if you really wanted to.

If you're wondering why we do this, the main reasons I'm aware of are that 1) The convention for big-O is that n always denotes "the length/size of the input", whether that input happens to be a tree with 50 nodes or an integer 50 digits long. So it's not as arbitrary as it might seem. 2) In practice the length/size of the input seems to be the limiting factor. The fact that I know a pseudo-polynomial time algorithm for prime factorization does not change the fact that I'll never be able to brute force an RSA private key with my laptop.

| improve this answer | |
  • I mostly understand your answer, but every time I learned about big-O N always referred to the number of elements existing in the data structure. I was looking for the disambiguation to tell the reader that N refers specifically to the input and further to the length. The point of the log is that if the input is a string with a-z, 0-9, and space as valid characters then the expression would be log base-37 of (N), also I didn't notice until just now I tried to wrap N in angled brackets but I guess that played hell with the html parser as such <N> – Mikeologist Apr 2 '16 at 12:42
  • @Mikeologist That's because 99% of the examples they use when discussing big-O are data structures. The definition of big-O doesn't say anything at all about what N is, and in fact any statement of big-O time complexity is completely meaningless if you don't know how N is defined. It's purely a convention that it refers to the number of items in a data structure, which is why it's hard to find a source that will come out and tell you that, and the slightly broader version of that convention is that it refers to the size or length of the input. – Ixrec Apr 2 '16 at 13:17
  • @Mikeologist By the way, your conclusion of O(log<sub>10</sub>⟨N⟩) is entirely correct when you define N as the value of the input, so there's no need to explain or defend it. – Ixrec Apr 2 '16 at 13:19
  • @lxrec Thank you. I am preparing to write a scholarly paper on this new data structure and I want to express all of it in mathematical and algorithmic expressions. The answer I needed to this question was direct confirmation of my statement. This you have provided between your answer and comments. So I have accepted your answer, upvoted it, and again my thanks. – Mikeologist Apr 2 '16 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.