-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 ?

Antzi
  • 105
  • 3
  • 2
    ...and not nearly enough information to perform a real Big-Oh analysis. –  Apr 02 '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. –  Apr 02 '15 at 17:40

1 Answers1

1

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

Becuzz
  • 4,815
  • 1
  • 21
  • 27
  • 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 02 '15 at 18:01