0

I had gone through many articles over internet to find minimum number in an array. According to article they iterate an array n number of times but purpose can be achieve n/2 + 1 iteration

Here is my code

for index in range(0, int(len(myArray)/2)+1):
 if minNum > myArray[index]:
    minNum = myArray[index]

 lastElement = - index - 1

 if minNum > myArray[lastElement]:
    minNum = myArray[lastElement]

Article code

for element in myArray:
  if minNum > element:
    minNum = element

Update my code to 

for index in range(0, int(len(myArray)/2)+1):
 if minNum > myArray[index]:
    minNum = myArray[index]

 if minNum > myArray[- index - 1]:
    minNum = myArray[- index - 1]

Is there is any reason why they used n iteration

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
rahul
  • 1,062
  • 5
  • 15
  • 31
  • 1
    Both variants perform the same number of comparisons. – AlexP Dec 02 '18 at 06:28
  • @AlexP but number of iteration is less – rahul Dec 02 '18 at 06:29
  • 1
    Your code is also iterating over all the elements. The only difference is that you iterate half of the array from the end to the middle. – Guy Dec 02 '18 at 06:30
  • @VidorVistrom it working correctly i tried on my local for given array – rahul Dec 02 '18 at 06:32
  • @Guy If i m not wrong iterating half decrease complexity – rahul Dec 02 '18 at 06:33
  • @rahul I meant you iterate the second half of the array with `lastElement` logic, the loop iterates the first half. – Guy Dec 02 '18 at 06:35
  • 1
    It is the exact same complexity because you perform the exact same number of operations. A decent optimizing compiler should be able to go automatically from the second variant to the first variant by loop unrolling it it considers that it would speed up execution. – AlexP Dec 02 '18 at 06:36
  • @rahul aah! My bad. I missed to see the indentations. You are however performing n comparisons which I failed to see because of indentations – Pushan Gupta Dec 02 '18 at 06:38
  • Each number that is not the minimum number must be compared to at least one other number. So we must have at least `n - 1` comparisons. I do not see how there can be any speedup. – hilberts_drinking_problem Dec 02 '18 at 06:45
  • That's why algorithms are dealt in Big-O. Small optimizations like these wouldn't change anything in the bigger picture. – Vineeth Chitteti Dec 02 '18 at 09:29
  • Since you're splitting for half iteration and expecting it to work 2X faster, why not split it into 1/3 iteration, or split 1/4 ...Or Split 1/n times.. you see where I'm getting right. If you split 1/n times you still need to perform n operations. The total number of operations are going to remain the same. – Vineeth Chitteti Dec 02 '18 at 12:08

1 Answers1

3

Your code has a small overhead and is actually slower than the article code.

I have made a small program that compares the execution time for both

Check this.

Explanation:

In the legacy style,

The loop runs for n times and make 1 comparison every time. Thus abruptly speaking, it takes, O(n) time. In your code the loop runs for around n/2 times and makes 2 comparisons every time plus the overhead of initializing the

lastElement

Thus although both take around O(n) times but the solution OP provides should run slower in most cases

OP's answer could run faster in the case when the degree of sorting is high. Processing sorted arrays is much faster.

Pushan Gupta
  • 3,697
  • 5
  • 23
  • 39
  • Thanks all for review and reply. If edit above code and instead of initialize lastElement variable, direclty pass "- index -1" in array like this "if minNum > myArray[- index - 1]: minNum = myArray[- index - 1]" then time complexity is less for my code then article code. Have a look and share your view – rahul Dec 02 '18 at 09:15
  • From your own page, after executing the code multiple times, many solutions showed negative result: The original comparison: 0.11443901062 OP's execution time was faster: 0.117331027985 OP's time is faster by: -0.0028920173645 – Vineeth Chitteti Dec 02 '18 at 09:25
  • @VineethChitteti thats why I said MOST cases. It depends upon how sorted our array is. Looping through a sorted array is much faster in terms of branching. Of course looping through a complete sorted array and a half looping through a sorted array, the latter wins. This is just one scenerio where the OP's result wins and hence I used MOST – Pushan Gupta Dec 02 '18 at 12:46
  • Thanks guys for the great discussion – rahul Dec 02 '18 at 14:26
  • @VidorVistrom makes sense. (Thumbs_up). Can you highlight 'most' in the post, so I can upvote :). Cheers. thanks. – Vineeth Chitteti Dec 02 '18 at 14:37
  • @VineethChitteti the most reasonable case I can think of where OP's answer is faster is the sorted case. Check [this](https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array) out. So the degree of sorting plays a major role – Pushan Gupta Dec 02 '18 at 18:17
  • @VidorVistrom, true. I have downvoted this answer first after I read. My bad. Now I can't upvote it unless you edit something in the answer. Can you please make an edit., so I can upvote :) – Vineeth Chitteti Dec 03 '18 at 19:41
  • @VineethChitteti sure :) – Pushan Gupta Dec 03 '18 at 21:44