CODEWITHSUNDEEP
algorithmbig-o
Julfikar
Julfikar

Reputation: 1423

Big-O for while loops with user input

Suppose Module X requires p units of time to be executed, where p is a constant. Find the complexity of each of the following algorithm where n is the size of the input data and q is a positive integer greater than 1. What will be the time complexity?

set i = 1
   `while i ≤ n` 
      `Module X` 
      `i = q * i` 
    endwhile

Upvotes: 1

Views: 85

Answers (1)

wookie919
wookie919

Reputation: 3134

log(n) where the base of the logarithmic function is q.

Hint: i increases exponentially.

Upvotes: 1

Related Questions