Chapter 2: Introduction to Algorithm Design

Question 1

Find the time complexity of the following Python snippets:

1. i=1 
   while(i<n): 
       i*=2 
       print("data")
   

2. i =n
   while(i>0):
       print("complexity")
       i/ = 2
   

3. for i in range(1,n):
       j = i 
       while(j<n):
           j*=2
   

4. i=1
   while(i<n): 
       print("python")
       i = i**2
   

Solution

1. The complexity will be O(log(n)).

   As we are multiplying the integer i by 2 in each step there will be exactly log(n) steps. (1, 2, 4, …… till n).

2. The complexity will be O(log(n)).

   As we are dividing the integer i by 2 in each step there will be exactly log(n) steps. (n, n/2, n/4, …… till 1).

3. The outer loop will run n times for each i in the outer loop, while the inner while loop will run log(i) times because we are multiplying...