A&DS Time complexity

Loops

The more nested loops there are, slower the code is.
Formula is k
O(n ) where k is the amount of loop nesting.

for (int i = 0; i <= n; i++){

// code
}

Complexity for the above code is O(n)

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {
// code
}
}

For this one though, its 2

O(n )

Phases

If there are multiple for loops in succession, the one with most complexity is dominant,
because it usually bottlenecks the code.

for (int i = 1; i <= n; i++) {

// code
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// code
}
}
for (int i = 1; i <= n; i++) {
// code
}

Time complexity of the above code would be 2

O(n ) (because of the second loop, which has
another one nested)

Several variables

If we have several variables in the loops, the complexity is multiple of them.

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {
// code
}
}

Complexity would be O(nm)

Recursion

If n input causes n calls, then the complexity is O(n).

If each call causes 2 calls, then time complexity grows to O(2
n
.
)

Read about Recurrence Relation.

Different kinds of complexity

O(1) - Running time of a Constant-time algorithm. It doesn't depend on the input.

O(log n) - A logarithmic algorithm usually halves the input size at each step (Divide and
conquer). It is logarithmic because log 2 n equals the number of times n must be divided by 2 to
get 1.

O(√n) - A square root algorithm. It finishes faster than linear algorithms, but slower than
logarithmic ones. For example, Finding the amount of divisors for a number
(We loop from 1 to √n to find all divisors, no number above √n will be able to divide n.)

O(n) - A Linear algorithm goes through the input the amount input times. It's usually the best
complexity for a function. Example of this is an unnested for loop.

O(n log n) - Algorithm likely sorts the input or uses a data structure which requires O(log n) time
each iteration.

O(n )
2
A quadratic algorithm often contains two nested loops. It is possible to go through all
pairs of the input elements in 2
O(n ) time.

O(n )
3
A cubic algorithm often contains three nested loops. It is possible to go through all
triplets of the input elements in O(n )
3
time.

O(2
n
) This time complexity often indicates that the algorithm iterates through all subsets of
the input elements. For example, the subsets of {1, 2, 3} are
∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} and {1, 2, 3}.

O(n!)This time complexity often indicates that the algorithm iterates through all permutations
of the input elements. For example, the permutations of {1, 2, 3} are
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) and (3, 2, 1) .

An algorithm is Polynomial if its time complexity is at most n

k
. All except the last two above
are polynomial. This usually means that the algorithm is efficient.

...To get an efficient algorithm (under 1 second)

input size required time complexity

n ≤ 10 O(n!)

n ≤ 20 O(2
n
)

n ≤ 500 O(n )
3

n ≤ 5000 O(n )
2

n ≤ 10
6
O(n log n) or O(n)

n is large O(1) or O(log n)