Question

1. Write a while loop whose time is θ(log n).

Answer 1

Most classical example of a while loop whose time complexity is Logn is iterative approach of Binary Search.

Have a look at the below Python Code...

def binary_search(arr,n,low,high,x):

  low = 0

  high = n-1 

  while low<=high:

    mid = low + (high-low)//2 

    if arr[mid]==x:

      return mid 
    
    elif arr[mid]<x:
      low = mid + 1 

    else:

      high = mid - 1

The time complexity of above code is O(logn). If parameter of any loop gets divided or multiplied by a constant number then the time complexity of that loop will be logn .

And we all know that time complexity of binary search is logn.

Happy Learning!