0

I was coding for a simple question on codeforces. It reads like this:

Vasya has n pairs of socks. In the morning of each day Vasya has to put on a pair of socks before he goes to school. When he comes home in the evening, Vasya takes off the used socks and throws them away. Every m-th day (at days with numbers m, 2m, 3m, ...) mom buys a pair of socks to Vasya. She does it late in the evening, so that Vasya cannot put on a new pair of socks before the next day. How many consecutive days pass until Vasya runs out of socks?

Input

The single line contains two integers n and m (1 ≤ n ≤ 100; 2 ≤ m ≤ 100), separated by a space.

Output

Print a single integer — the answer to the problem.

My solution is this : 

int main()
{
    int res,i,n,m;
    cin >> n >> m;

    i = 1;
    res = n;
    while(res >= i*m)
    {
        res++;
        i++;
    }

    cout << res;
    return 0;
}

What should be the time complexity? Its definitely not O(n), as we are increasing in steps of m. Will it be log n (base m)? But also the original n increases with time !!!

Please put some justifications.

Naveen
  • 7,944
  • 12
  • 78
  • 165
  • 1
    Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – ivan_pozdeev May 15 '16 at 09:14

2 Answers2

1

The biggest factor in the RAM computation model would be:

while(res >= i*m)
{
    res++;
    i++;
}

The bounding factor will be:

n + i < i*m since res starts at n and grows at the same rate as i

i*m-i > n

i > n / (m-1)

Since we are dealing with integer values here, an additional bound will be

i >= 1

The algorithm will grow with O(n/m)

bashrc
  • 4,725
  • 1
  • 22
  • 49
0

it's a very nice coding... to find time complexity we can ignore here the increment of n as m is chasing behind with multiples of increment on its own value like 1m,2m,3m,so we can ignore additional increments over multiple increments....so while loop will iterate here upto what multiples of m to overdo the value of n (ignoring n's increment).. And complexity evidently O(n/m) . And for the consecutive days dat the girl will be running out of sock u can print the value of (m*i-res)...

RahulCoffee
  • 56
  • 11
  • I don't agree with "very nice coding". The original problem is solvable with no loops and with time complexity O(1). – Patricia Shanahan May 15 '16 at 20:32
  • The question was not "How best to solve the problem", but "What is the complexity of this algorithm?" so direct posting would be off-topic. See (http://codeforces.com/blog/entry/13465?locale=en) for a formula for calculating the time without looping. – Patricia Shanahan May 15 '16 at 21:57