0

I am new to algorithm analysis, so I appreciate if anyone can help me. I have the following algorithm for sorting an array:

for(int i = 0 ; i < list ; i++){
    if(list[i] > list[i+1]){
       swap list[i] with list[i+1]
       i = -1;
    }
}

I claim that this algorithm is a linear algorithm (i.e, O(n)) but I did not know how to prove this.

I appreciate any help. Thanks in advance.

Hussein Eid
  • 209
  • 2
  • 9
  • Analyse what happens in a simple worst case situation, e.g. input = [4 3 2 1] – Damien Jun 06 '20 at 16:53
  • `Big O` in O(n) indicates the worst case and n is a variable value which is not fixed, which depends upon the size of `list` in case of your example. As for loop will iterate till the size of the list. Hence it has been denoted as `n` which is dependent on list size. – Nitin Bisht Jun 06 '20 at 16:54
  • That is not an algorithm for sorting (arbitrary) arrays. At least, not a complete and correct one. – John Bollinger Jun 06 '20 at 17:02
  • That is what I really did. I also considered the same example you considered. I traced the code well. But, unfortunately, I could not deduce the order of the time complexity in general. @Damien – Hussein Eid Jun 06 '20 at 17:03
  • Excuse me, I think you are a little mistaken because there is a condition `i = -1` inside the loop body which will force the loop to restart. @NitinBisht – Hussein Eid Jun 06 '20 at 17:05
  • Please have a look at the link provided by @PaulHankin – Damien Jun 06 '20 at 17:05
  • @HusseinEid doesn't matter in case of Big O we always talk about the worst case. – Nitin Bisht Jun 06 '20 at 17:07
  • I am reading it right now @Damien – Hussein Eid Jun 06 '20 at 17:08
  • I got it. The recurrence relation the time complexity of the algorithm satisfies is: `T(n)=T(n-1) + (n-1)(n-2)/2` . I solved this recurrence by backward substitutions, and I found that it is `O(n²)`. But the answer provided by @PaulHankin says that it is `O(n³)` . Why?. – Hussein Eid Jun 06 '20 at 17:32
  • You made a mistake. `https://www.wolframalpha.com/input/?i=sum%28%28i-1%29*%28i-2%29%2F2%2C+i+%3D+1..n%29` gives `sum_(i=1)^n 1/2 (i - 1) (i - 2) = 1/6 n (n^2 - 3 n + 2)` which is O(n^3). – Paul Hankin Jun 07 '20 at 05:43

1 Answers1

0

This algorithm is actually cubic (O(n^3) where n = length of list) in the worst case scenario. Imagine the following input: list = [5,4,3,2,1].

First iteration: list[0] > list[1]. The swap is made such that list = [4,5,3,2,1], and i is reduced to -1, so the loop starts over.

Second iteration: list[0] < list[1].

Third iteration: list[1] > list[2]. The swap is made such that list = [4,3,5,2,1], and i is reduced to -1, so the loop starts over.

Fourth iteration: list[0] > list[1]. The swap is made such that list = [3,4,5,2,1], and i is reduced to -1, so the loop starts over.

The same pattern continues: we will need 6 more iterations to bring 2 to the start of the list, 10 iterations for 1, and 5 to skim over the list once it's all sorted. Overall 4+6+10+5=25 which is 5^2. So why n^3 and not n^2?

Intuition:

For a list that sorted in reverse like the one in the above example, we would need to bring each element to the head of the list from greatest to smallest. The j'th element in the initial list is the j'th greatest overall and will need (1+2+...+j)=O(j^2) steps to bring to the head of the list. Therefore, in order to reverse the list of length n, we need approximately (1^2 + 2^2 + ... + n^2) steps. That is the sum of squares from 1 to n which is O(n^3) - if you don't know why, it's a very well-known formula in arithmetics: sum of squares.

Disclaimer: Of course, it wouldn't be exactly n^3 steps, but it will be approximately so (which is after all the definition of Big-O notation. It will be closer to n^3 the bigger n gets).

Yaron Grushka
  • 235
  • 2
  • 10