How is the time complexity of an algorithm calculated if there are two complexities in the algorithm?

Question

Algorithms

I have an algorithm. It consists of several parts. The first part is performed with O(N) complexity, the second with O(log(N) complexity). What is the complexity of the algorithm in this case? Is the largest taken or do these parts somehow add up?

Answer 1

Yes, the largest is taken, in this case O(N).

Answer 2

On the fingers - you can add and take more. But the latter is a more accurate estimate. But in fact, it is necessary to formally paint by definition. What does the first part O(N) mean? For some numbers N1 and C1, for N>N1 the first part of the algorithm does less than C1*N operations. Similarly, for N>N2, the second part performs less than С2*log(N) operations.
In total, we have, for N>max(N1,N2), less than C1*N+C2*logN operations are performed in total. If we take C = max(C1, C2), then we can limit the number of operations C*(N+log N) from above. Those. we have proved that your algorithm is O(N+log N). Further, starting from some N>N3 N > log(N). Those. for N> max(N1,N2,N3) you can limit the running time as C*(N+N) = 2*C*N = C'*N. And this already means that the whole algorithm is O (N).
From these considerations, it should be clear that with a constant number of steps, you can take O () for the heaviest step. But, if the number of steps depends on N, then this cannot be done, because in the last step, not a constant factor will come out (like 2 above), but something that depends on N.