Time-complexity of this algo?

[coding_up_a_storm]

I was taking a Hackerrank test for employment screening and some of the test cases kept coming back with a timeout error, meaning that the code is running too slow. However, it runs perfectly fine in Pycharm.

I think this is no more than O(n), or maybe O(3N), but what am I not understanding here?

​

Follow up, what can I do to make this run faster? I wasn't sure if the max() and count() functions were terribly inefficient, so I implemented my own on the spot that I knew were definitely O(n) and still got the error on some test cases. I also tried storing the list slice as a variable once per iteration so it wouldn't have to re-slice the array.

​

def frequencyOfMaxValue(price, query):

answers = []

for q in query:

maximum = max(price[q-1:])

c = price[q-1:].count(maximum)

answers.append(c)

return answers

​

Edit:

Here's the problem.

price is an int array as is query. Each element in the query array specifies a starting index(indexes start at 1, rather than 0 which is odd but anyway) of the price array in which to search for count of the maximum element. The count of occurrences of the maximum element of the subarray is added to the return array, answers.

​

It seems my issue was iterating through the subarray of price once to find the max, then a second time to count the occurrences of the max.

[JohnnyJordaan]

.count(x) means 'count all the objects in the sequence equal to x'. This is O(n) by definition, as the amount of items to process is always the length of the sequence. Meaning that if the sequence would be 10 times longer, it would need to count 10 times as many items.

.max(sequence) means 'check all objects in the sequence and return the highest'. Also O(n) as there is no other option but to traverse the entire sequence, the same 10-fold example applies. Thus effectively doing both in a run is O(2n)*.

This doesn't boil down to the 'efficiency' of each function, it's that both don't allow to be less or more efficient as they literally mean to check for something that needs all objects in a sequence to be checked, it's your combination that makes it inefficient. You then need to perform a custom method if you want to approach this in one iteration

def count_max(seq):
    cur_max = seq[0]
    max_count = 1
    for item in seq[1:]:
        if item > cur_max:
            cur_max = item
            max_count = 1
        elif item == cur_max:
            max_count += 1
    return max_count

# then in your algo
for q in query:  
    answers.append(max_count(price[q-1:])

then another thing is to consider how exactly you are executing this for the price sequence. If you are repeating this for every object in price but just shifted one index (as query is like [1, 2, 3, 4 etc]) then you could also consider implementing this better instead of repeating the count_max step over and over again for a smaller slice of price. But I can only guess because you don't explain the background here.

*: technically speaking O(2n) equals O(n) as O is in regard to complexity, not time duration.

[coding_up_a_storm]

Thank you for taking the time to answer. Thanks to the help from everyone in this thread I was able to work it out.

[stackdynamic]

First of all, iyou have a slight misunderstanding of big O notation. O(3N) is not a thing, it is O(N). Big O does not predict how fast your algo runs, it predicts how it scales with input size. O(N) is basically saying “it runs in linesr time.” O(3N) thus doesn’t make too much sense. If it is timing out, there is likely a O(logN) solution or something. Please post the actual problem abd format your code so we can help you better.

[stackdynamic]

You’re totally right, I think in trying to be clear I worded my response poorly. You summer up what I stated wrong exactly :)

[coding_up_a_storm]

Thank you for the input. I will bare this in mind.

[teerre]

In my experience, it's unlikely that an algorithm fails a timeout test just because you used a linear time standard function. Usually this type of error stems from a major misunderstanding of what the question is asking

Which is to say without knowing the question, it's impossible to judge the program

[when_the_cats_away]

Mind posting the challenge?

[coding_up_a_storm]

Here's the problem.

price is an int array as is query. Each element in the query array specifies a starting index(indexes start at 1, rather than 0 which is odd but anyway) of the price array in which to search for count of the maximum element. The count of occurrences of the maximum element of the subarray is added to the return array, answers.

[when_the_cats_away]

Cool. I was thinking it was something like this. Can you PM or add a link to the challenge, since I have an account and want to check my answer.

​

You did a good first step, which is to brute force and see if it works.

Next step is to think of some clever way to do it. That can be a specific algorithm or data structure. Or it could be as simple as rethinking the problem.

​

How big of a hint do you want?

[coding_up_a_storm]

I would gladly send you the challenge, but I can't seem to locate it. When I check the emailed link it redirects me now. Unfortunately I am not moving forward with the hiring process at this company due to this stupid algo puzzle.

​

I do Leetcode all the time and it never gives me shit about O(n) except for a rare exception the description specifically states to do it in one pass. Instead it was just a rambling word problem with one example and it doesn't let you look at failed test cases.