Time Complexity Analysis - Odd Even - Big Jumps

Question

j = 1
while ( j < n ) {
     k = j
     while ( k < n ) {
          If  ( k is odd )
              k++
          else   
              k + = 0.01 * n
    }
    j+=0.1*n
}

Answer 1

It should be O(1).

The two loop will end in a constant time.

----------------------------

Of course, supplementary：

(1) Consider the outside loop, j will be j+0.1n after each iteration, (note here it's about n, n is a constant). Therefore, after 10 times, the original j will be j+n which is greater than n, the outside loop ends.

(2) Now consider the inside loop, it's similar, except a if statement, but it doesn't matter, after 100 times, the same thing happen again, the original k becomes k+n which will cause the end of the inside loop.

(3) Why the if condition doesn't matter? Consider k is odd, k will be k+1 which becomes even, and then do the 100 iterations. Consider k is an even, it does 100 iterations directly. that's why if condition is a trap.

(4) Combine step 1 and 2, the two loops will end no more than 10 and 100 times no matter what n is, which is an constant. that's O(1).

Comments

If you can substantiate more on why it should be O(1), I will be happy to mark this as the correct answer.

Answer 2

Sorry I answered too carelessly last time. After consideration this question is much more complicated than I thought. So here I will discuss according to different conditions:

First we see the outside while loop. J is increased by 0.1*n. So after 10 times J will be more than n.

Here according to different n, j will be increased into different numbers such as even odd or floating number, which will further influence the if else condition in the inner loop.

However, we can see that the condition of if sentence is that when k is odd, and then the statement is K++, so next step k will absolutely be a even number. What does this mean? 

Case1

This means for the best assumption, the if condition when k is odd will be executed at most as same times as the else condition, where 0.01n should be odd number which means n is odd number times hundred as well as the initial value of k is integer. And here if we check into deeper details, we can find that the case when initial k is integer we must have J+=0.1*n  to be integer.  So lets discuss that when we want 0.01n to be odd(surely 0.1n will be integer too), we have 1/200 chance for every n value that is possible to be input(i.e. when n is input from 1 - 1000, we only have 100, 300, 500, 700 and 900 that meet requirement for all the 1000 numbers). So it would be a quite rare condition to meet all these requirements. Temporarily we don't know whether it will have impact on the worst case, we will discuss this later.

Case2

Then, what is the case that 0.1*n is integer but 0.01*n is not odd which will happen more than the case about? in this case, even if k initial is odd, it will soon be even because the statement is K++. And then because 0.01n is floating number, so the case K+= 0.01n will dominate until k surpasses n. So here for the ten initial values k will get: 1, 1+0.1n, 1+0.2n, 1+0.3n ... 1+0.9n. we will have 0.01n*t <= n-1, 0.01n*t<=0.9n -1 0.01n*t <=0.8n -1... 0.01n*t <= 0.1n -1. t = (n-1)/0.01n ...t = (0.1n -1)/0.01n. assume n is a big number, then the result will be simplified as sum = 100 + 90 + 80 + ... 10 = 550 constant time. Here since k+0.01n dominates, 0.1n is integer has no meaning any more, the case 0.1n is floating number and 0.01*n is not odd have the same time complexity.

Case3

Afterwards, the case 0.1*n is not integer but 0.01*n is odd is not possible.

Case4

 Another case is that when 0.1n is integer but 0.01n is xxx.5. Here when the else condition k = +0.01n operate two times, k value will be odd again, so its like 1/3 of total time execute k++ 2/3 of time execute k += 0.01n. so for the ten time outloop operation, the inner operation will be 1/3*t + 2/3*0.01n*t <=n....1/3*t + 2/3*0.01n*t <=0.1n, here t = 3n/(1 + 0.02n)...t = 0.3n/(1 + 0.02n). sum = 16.5n/(1+0.02n)

when 0.02n is much bigger than 1, i.e. n = 5000, t = 825 times.

when 0.02n is close to 1, i.e. n = 500, t = 750

when 0.02n is equal to 1, n = 50, t = 412.5

...the trend is decreasing, so we just take larger n into account.

Case4.1

here I have two observations, the first one is that there are many more conditions like 4*0.01n is odd or 6* 0.01n is odd, the ratio of time will be 1/5 4/5 and 1/7 6/7, the sum of t will be 684 when n = 5000 for 1/5 ratio, and 639.5 for n = 5000 for 1/7 ratio. and finally it will be infinitely closer to 550 because 0.01n will increase more than 1 and the chance 0.01n happen is also increasing, and finally the condition became case 2 we talked above.

Case4.2

However, when n is small, then 0.01n and 1 all have visible impact on the time complexity, but, since n is small, we can get k more than n easily so the total time will not surpass 825 times.

for the case that k+=0.1n is floating number but k+=0.01n will make k back to odd again, the process is similar above, so we don't discuss it and take the result above.

Here we can see that whether k+=0.1n is integer or floating number actually don't meaning too much. the key point is how many time does k+=0.01 and k++ takes.

Case5

Finally we get into the worst case. in this case, the initial value of k is integer and 0.01n is odd. Here the ratio is 1/2 1/2, and the total time cost will be 1078 times. actually this is also a alternative to the condition that k is integer and 0.01n is xxx.5.

for n quite small, the time it cost will just be smaller. 

Overall

so overall, the average time cost is 550 for both 0.1n and 0.01n are floating numbers and the worst case is 1078 for k is integer and 0.01n is odd.

sorry for the long and disordered answer, in summary, here are three things to consider. 

1.the ratio of if condition and else condition that will be operated. 

2.the value of n, whether 1 has much more contribution to the adding process or 0.01n has more.

3.Then the average condition is that numbers are always floating numbers and we execute k+=0.01n only. this is the most condition.

Hope this is readable lol

Answer 3

In the while loop, k increases in this manner: half of time it increases by 1 and another half time by 0.01*n

So we can say that assume t is the time it runs in while loop,

1/2*t + 1/2*t*0.01*n <= n

1/2*t*(1+0.01*n) <= n

t <= 2n/(1+0.01n) // first time

t<=2(n-1)/(1+0.01n) // second time

.

.

.

t<= 2/(1+0.01n) for the last time

sum of t is n²/(1 + 0.01n)

and since 1+0.01n should be theta(n), so n²/(1+0.01n) is n²/n = O(n)

Comments

I think k is not half time k++ and half time +=0.01*n. Because the k+=0.01*n happens more frequently than k++.

---

Hey buddy, the if else condition is that if k is odd, blabla, so else is if k is even, then blabla, k is also increased by 1 each time

---

It may be a good idea to analyze these 2 loops independently.

---

I am assuming when 0.01*n is even number or when 0.01*n is floating number, the time complexity should be constant since it will stay on the else loop and takes at most 100 times to escape the inner loop and the outer while will take at most 10 times.  I can't give a strict proof so it would be great if anyone can help.  I guess while 0.01*n is odd, then the condition would be like Jian's answer.

---

Yeah you are right, the time of running even and odd is different, I made a wrong analysis

---

you are right, its not half and half, I will update it later.

---

You created a lot of inspiration. Thanks man. Look forward to your answer