When to add and when to multiply to find time complexity [duplicate]

This question already has an answer here:

I am trying to learn how to determine time complexity. Sometimes, I see complexity as $$\log n + \log n = 2\log n$$ but sometimes I see complexity as $$\log n\cdot\log n$$ which is $$(\log n)^2$$.

Suppose I need to do two binary searches to find two different elements, in one algorithm. Is this $$\log n + \log n$$ time, or would it be $$(\log n)^2$$ time?

marked as duplicate by Raphael♦Nov 18 '18 at 15:38

Don't look for rules that you can follow. Try to understand what is actually going on and then write down the mathematics that expresses that.

You would, I hope, have no difficulty answering the following questions:

• If I have a line of $$m$$ bricks and a line of $$n$$ bricks, how many bricks do I have?
• If I want to build a wall that is $$m$$ bricks tall and $$n$$ bricks wide, how many bricks do I need?

Use the same sort of reasoning to figure out what is going on in complexity analyses.

You add time complexities when you have something of the form: do operation $$A$$, then do operation $$B$$. This would be (time complexity of $$A$$) + (time complexity of $$B$$).

You multiply time complexities when you have something of the form: do operation $$A$$, $$X$$ times (eg. in a for loop). This would be $$X \cdot$$(time complexity of $$A$$).

If you perform two binary searches, each of which has time complexity $$\log n$$, the total runtime is $$\log n + \log n$$. You might see a runtime of $$(\log n)^2$$ if you had to perform $$\log n$$ binary searches.