Is it possible to find two numbers whose difference is minimum in O(n) time

by

Find smallest and largest element in the list. The difference smallest-largest will be minimum.

If you’re looking for nonnegative difference, then this is of course at least as hard as checking if the array has two same elements. This is called element uniqueness problem and without any additional assumptions (like limiting size of integers, allowing other operations than comparison) requires >= n log n time. It is the 1-dimensional case of finding the closest pair of points.

More Related Contents:

  1. Big O, how do you calculate/approximate it?
  2. Fastest sort of fixed length 6 int array
  3. What is an Efficient algorithm to find Area of Overlapping Rectangles
  4. Finding closest neighbour using optimized Levenshtein Algorithm
  5. How to calculate or approximate the median of a list without storing the list
  6. Most efficient way to calculate Levenshtein distance
  7. Faster version of find for sorted vectors (MATLAB)
  8. Why is my recursive function so slow in R?
  9. Why is the “start small” algorithm for branch displacement not optimal?
  10. 64/32-bit division on a processor with 32/16-bit division
  11. Efficient way to add element to sorted datastructure [closed]
  12. How to count the number of set bits in a 32-bit integer?
  13. Algorithm to return all combinations of k elements from n
  14. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  15. How do you detect Credit card type based on number?
  16. Millions of 3D points: How to find the 10 of them closest to a given point?
  17. Algorithm to randomly generate an aesthetically-pleasing color palette [closed]
  18. How to efficiently build a tree from a flat structure?
  19. What is a good Hash Function?
  20. Binary Search in Array
  21. The Sieve of Atkin
  22. Longest acyclic path in a directed unweighted graph
  23. 3 dimensional bin packing algorithms
  24. Circular approximation of polygon (or its part)
  25. How can I create an internal spiral for a polygon?
  26. Finding the best trade-off point on a curve
  27. what is the fastest way to find the gcd of n numbers?
  28. Algorithm for reflecting a point across a line
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment