Junsoo Park

Exercises 

Calculate the time complexities for each of the exercise code snippets

Exercise 1

Exercise 2

Exercise 3

 

 

Exercise 4

 

 

Exercise 5

 

 

Exercise 5

 

Answer

1. O(n²)
   There are two nested loops. Ignore the constants in front of n.
2. O(n³)
   There are four nested loops, but the last loop runs only until 10.
3. O(1)
   Constant complexity. The function runs from 0 to 1000. This does not depend on n.
4. O(n)
   Linear complexity. The function runs from 0 to 10n. Constants are ignored in Big-O
5. O(log₂n)
   Logarithmic complexity. For a given n, this will operate only log₂n times because i is incremented by multiplying by 2 rather than adding 1 as in the other examples.
6. O(∞)
   Infinite loop. This function will not end