Results 1 to 2 of 2

Thread: Algorithms which approach is faster?

  1. #1
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    46

    Question Algorithms which approach is faster?

    Algorithms which approach is faster?-sort.png
    Solution 1:

    Without sort:
    Loop over numbers in array
    match each number with K, increment the count if match.
    Time complexity: O(n)
    With sort:
    Sort numbers O(nlogn)
    Find first and last index of k using binary search 2*logn = O(logn)
    Count= last index - first index + 1
    Time complexity: O(nlogn)
    Here, Without sort approach is always best.

    Solution 2:


    1. traverse whole array and increase count from 0 to +1 every time we encounter the element
    so running time will be O(n) for traversal and comparision and O(1) for count increase so finally we have running time of O(n)
    2. faster approach:
    first sort the array afterwords we can use binary search method to count the occurrences and its running time complexity will be O(log(n))

    Which solution would be better from the two?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2018
    From
    Europe
    Posts
    3

    Re: Algorithms which approach is faster?

    I don't really see the difference between solution 1 & 2. The only difference seems to be that you ignore the cost of sorting in solution 2.2. I guess it could make sense if you want to find the count of many different numbers and you don't care about how long it takes to sort the array because it's only done once. Well, in that case O(log n) is better than O(n) so solution 2.2 would be the winner over 2.1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Dec 18th 2011, 06:13 PM
  2. Faster way ?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 24th 2010, 12:40 AM
  3. Any approach other than axiomatic approach to Real Numbers
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 11th 2010, 01:21 PM
  4. I need a faster way of doing this
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jul 28th 2008, 09:58 PM
  5. Who is faster???
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jun 15th 2006, 05:29 PM

/mathhelpforum @mathhelpforum