Examples Related to Time Complexities
Let's dive deeper into the time complexity analysis by looking into some examples in this lesson.
We'll cover the following...
- Example 1: for loop
- Example 2: Nested for loop
- Example 3: Arithmetic series
- Example 4: Double the iteration variable
- Example 5: Half the iteration variable
- Example 6: Square root iteration
- Example 7: Nested loop in O(n)
- Example 8: Arithmetic progression
- Example 9: Triple nested loop
- Example 10: Multiple loops in O(n)
Letās dive deeper into the time complexity analysis by looking at some examples.
Example 1: for loop
The case below is a for loop. We have a time complexity of .
Press + to interact
package mainimport("fmt")func fun1(n int) int {m := 0for i := 0; i < n; i++ {m += 1}return m}func main() {fmt.Println("N = 100, Number of instructions O(n) ::", fun1(100))}
The statement on line 10 takes constant time. Hence, it doesnāt affect the time complexity of the loop.
Example 2: Nested for loop
In this case, we have a nested loop where the total number of loops is 2. Both loops run n times. According to formula , its time complexity is .
Press + to interact
package mainimport("fmt")func fun2(n int) int {m := 0for i := 0; i < n; i++ {for j := 0; j < n; j++ {m += 1}}return m}func main() {fmt.Println("N = 100, Number of instructions O(n^2) ::", fun2(100))}
Example 3: Arithmetic series
This example shows that the inner loop iterates times, and the outer loop iterates times.
The exact number of steps will go the same way as those of the arithmetic series. In this case, the time complexity will be: = ...