Understanding the time complexity of given code

Question

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.

Answer 1

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)...

Answer 2

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)