Hi there,

I was watching a mock interview, and the candidate was asked to solve this problem, and he made the solution as shown in the picture:

He said time complexity would be O(log n), and the interviewer confirmed it.

I thought it is O(n), because the more digits in the integer, the more loops done by “while” loop, so the more the input size of this function, the more loops will be done.

integer of 3 digits, will take 3 loops

integer of 4 digits, will take 4 loops

and so on.

I don’t why I thought about it as number of digits, I feel something wrong in my way, but I don’t know how to think of increasing input when it is just a number not a size of something.

I think I should say it like this:

0 … 1 loop

5 … 1 loop

10 … 2 loops

50 … 2 loops

100 … 3 loops

500 … 3 loops

1000 … 4 loops

5000 … 4 loops

10000 … 5 loops

50000 … 5 loops

100000 … 6 loops

500000 … 6 loops

1000000 … 7 loops

etc…

integer | no. of loops |
---|---|

0 | 1 |

10 | 2 |

100 | 3 |

1000 | 4 |

10000 | 5 |

100000 | 6 |

1000000 | 7 |

Can anybody help how to think? how to read this code so it is a O(log n)?