Research Publications

Abstract

The Coin Change problem is to represent a given amount V with fewest number of coins m. As a variation of knapsack problem, it is known to be NP-hard problem. Most of the time, Greedy alogrithm (time complexity O(m), space complexity O(1)), irrespective of real money system, doesn’t give optimal solution. Dynamic algorithm (time complexity O(mV), space complexity O(V)) gives optimal solution but is still expensive as amount V can be very large. In this paper, we have presented a suboptimal solution for the coin change problem which is much better than the greedy algorithm and has accuracy comparable to dynamic solution. Moreover, comparison of different algorithms has been stated in this paper. Proposed algorithm has a time complexity of O(m2f) and space complexity of O(1), where f is the maximum number of times a coin can be used to make amount V. It is, most of the time, more efficient as compared to dynamic algorithm and uses no memoization, this is a significant advantage over dynamic approach.

Keywords

Abstract

The binary search is a method of finding the position of an element in an ordered array. It continuously aims the middle element of array and check if it is the target element or not untills it finds its position. The best case complexity of binary search is O(1), whereas average and worst case time complexity is O(log n), where ‘n’ is the number of elements in the array. In this paper, I have proposed an algorithm which drastically improves the complexity of search algorithm in sorted array domain outperforming binary search, the paper also compares the proposed solution with other well-known search algorithms. The presented approach minimizes the space complexity, eliminates the need to analyze the scenario and look for the algorithm that best fits the given problem. The proposed algorithm has constant space complexity (O(1)) and time complexity of O(1) (constant time) in best case, O(log(log n)) in average case and O(log(n)) in worst case. Thus, most of the time proposed algorithm works very well as compared to other search algorithms in sorted array domain.

Keywords