CODEWITHSUNDEEP
algorithmoptimizationbig-o
Jacob Scott
Jacob Scott

Reputation: 197

How to optimize following algorithm?

We have following algorithm:

while(a > b) {
     a -= c;
}

a, b and c are given, b and c are constants, c > 0.

Now it works in linear time. Is it possible to speed it up, to work in logarithmic or constant time?

Upvotes: 2

Views: 67

Answers (2)

Tempestas Ludi
Tempestas Ludi

Reputation: 1165

Uhm... You could try this, right (given that a, b and c are positive integers)?

a = (a-b)%c + b - c

Upvotes: 5

Juan Lopes
Juan Lopes

Reputation: 10575

Perform a binary search to find the minimum x such that a-x*c <= b.

Upvotes: 1

Related Questions