-2

I have a function for which the complexity raise by the square ten of the exponent of the number.

Ex:

+-----+----------+
|Input|Complexity|
+-----+----------+
|0    |     1    |
|10   |     2    |
|100  |     3    |
|123  |     3    |
|1001 |     4    |
|9999 |     4    |
|10000|     5    |
|99999|     5    |
+-----+----------+

How to express its complexity in big O notation ?

  • 2
    ...and not nearly enough information to perform a real Big-Oh analysis. – user22815 Apr 2 '15 at 17:23
  • I started editing the question to fix the grammar when I realized that the question would answer itself. Hint: if you define the relationship between "Input" and "Complexity" you will come up with the most likely answer, although the proof will be an analysis of the actual code. – user22815 Apr 2 '15 at 17:40
1

The mathematical function that is like that is log n. So the big O notation would be O(log n).

  • Log(n) is indeed very very close to the expected result, but slightly above. When giving a Big O notation, is it expected to be a (pretty accurate) approximation ? – Antzi Apr 2 '15 at 18:01

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