I should to solve this problem in the most efficient way for a school project but I can not determine the Order of Complexity.
For a given numer s>7, I should find a and b for which 3a+5b=s, a has the maximum possible value and b has the minimum possible value.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include<iostream>
usingnamespace std;
int main () {
long s, a, b, ok=0;
cin>>s;
for(a=s/3;a>=0&&ok==0;a--)
for(b=0;b<=s/5;b++) if((3*a+5*b)==s) {ok=1; break;}
cout<<endl<<++a<<' '<<b<<endl;
return 0;
}
The program works perfectly, but I can not determine its Order of Complexity. I think that is between O(n) and O(n2) but I want a more accurate determination . Can anyone help me? Is there a more efficient way to solve this problem?
I don't really know about O of this code. Nested for loops somehow imply n2, but the first loop will not run more than 4 times, so it will take from 1 to 4/5s cycles to find the answer, which looks like n..
Though I do know that the algorithm isn't good. This can be done in constant time.
Note that b will never be 3, as then it could be replaced by five 3s. It can only be 0, 1 or 2. Obviously it will be 0, hen s is divisible by 3. Can you figure out when it will be 1 or 2 ?