1

Why we write time complexity in terms of logarithm for some questions. For example In many problems log(n) time complexity.

Dhananjay Tawar
  • 35
  • 1
  • 7

2 Answers2

2

For divide-and-conquer algorithms each step reduces the task at hand by a factor of B. For example, each step of a binary search reduces the number of items you need to consider by a factor of two; ternary search reduces it by a factor of three, etc.

If you start with N items and need x steps to find the answer, then N is less than or equal to Bx, where B is the "reduction factor" of your algorithm.

Since logarithm lets you obtain x from Bx, we consider x to be O(logBN).

Finally, note that B can be factored out by using the change of base formula, so we remove B from the formula, and write O(log n) instead.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

Because some algorithms rely on splitting the input data in two equal part, then focusing on a single part and apply that recursively. The algorithm will work its way through the data by always splitting in half.

If you have an arbitrary array of size N, you can split that array in half log(N) times until you end up with partitions of size 1 (or less).

Remember that unless specified otherwise, Log in time complexity means Log base 2.

Arthur Attout
  • 2,701
  • 2
  • 26
  • 49
  • Why we use logarithm at all, what is need to use logarithm? – Dhananjay Tawar May 09 '21 at 12:53
  • If you check out the last statement in Sergey Kalinichenko's answer, you'll find that your own final sentence is incorrect. Logs in any base can be converted to any other base via scaling by a constant. Since big-O notation ignores constants there's no need to specify the base when talking about logarithmic complexities. – pjs May 09 '21 at 14:11
  • Indeed, I did not know about that subtility – Arthur Attout May 09 '21 at 14:17
  • @pjs That is not always true - for example O(n^log2 n) is not the same as O(n^log10 n). But when the base does matter, I think it should be written explicitly, not assumed to be 2 by default. – kaya3 May 09 '21 at 14:51
  • @kaya3 Agreed that you have to watch the base once you start exponentiating the logs. But it's still true that I could express the log portion itself as a log in any base scaled by a suitable constant. – pjs May 09 '21 at 15:00