Hacker Newsnew | comments | show | ask | jobs | submit login

OP's example accepts a parameter, and that parameter is the input size, not any of the input values. In fact, in the example, there are no input values, the function is just doing busy work -- although, I suppose it's also possible to say that i (0,1,2,3,...,n) are the values, since that's what he's printing. However, as you said, the individual input values are irrelevant to the complexity.

Consider this slightly modified function:

    f(string[] phonebook, int phonebookSize) {
      int i;
      for (i = 0; i < phonebookSize; ++i)
Here it's clear that phonebookSize (n) is the input size, not an input value -- however the function is essentially the same otherwise.

EDIT: Sorry, I understand now. You are saying that the way he's defined his function is what determines the input size. Since it accepts one integer, the complexity could be described as O(2^n) (where n is the size of the integer in bits, or digits, or whatever). I had made the assumption that my updated function is what OP's intention was.

I'm confused, wouldn't this be more of an O(n) instead of an O(log n) issue? If not, then what is the difference? No pointers being used, not even a data structure, just an array of strings. I expected at least a linked list data structure for a phone book. Like sorted in alphabetic order or something.


Correct, OP's example contained an O(n) function:

> For example, the following function is O(n) because the algorithm grows in proportion to its input n: [...]

OP's question was whether there exists a similarly simple example of O(log n), which is not related to what anonymouz was commenting on. (or I'm misunderstanding?)


Guidelines | FAQ | Support | API | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact