How is time complexity calculated?

Question

When we have a loop and iterate over all elements, the time complexity is O(n). But when we have multiple loops (not nested), the time complexity is still O(n). Why? Or am I wrong here?

Example code:

func findElement(input: [Int]) {
    for i in input { ... } // Loop1
    for i in input { ... } // Loop2
    for i in input { ... } // Loop3
}

Despite having three loops, the time complexity is O(n). Why?

Answer 1

When writing the complexity, there are some rules to follow.

1. multiplicative constants should be removed
2. additive constants should be removed
3. terms of smaller power should be removed

In a nutshell, these rules apply because when your input grows to infinite, these removed terms tend to have a negligible value in comparison to the remaining term and will not affect the shape of the asymptote formed by the complexity function.

example 1:

O(3n² + 2nlog(n) + 4n + 10)    applying (2)
O(3n² + 2nlog(n) + 4n)         applying (3)
O(3n²)                         applying (1)
O(n²) 

example 2:

O(0.4n + 3log(n))                applying (3)
O(0.4n)                          applying (1)
O(n)    

In your code, there are 3 loops, which totalize O(3n). Applying (1), you get O(n). If the loops were nested, it would be O(n.n.n) = O(n³).