Hey, so I need to write an algorithm that will do the following and run in O(n):
Search linearly through an array of size n and for each element check whether array>array[i-k] for all k=1,2,...n/5.
Its easy to do this with two loops but I cant figure out how to do this in O(n).
Is this a trick question? If array > array[i-1] for all i, then surely array > array[i-k] for all positive values of k. So you can ignore the inner loop. Or am I missig something?
Is this a trick question? If array > array[i-1] for all i, then surely array > array[i-k] for all positive values of k. So you can ignore the inner loop. Or am I missig something?
its not a sorted array.
its not a sorted array.
Did anyone say it was?
Did anyone say it was?
Well, I think you may be making an assumption of the value of any given element of the array. array may point to a value 7 where array may point to a value of 77.
Search linearly through an array of size n and for each element check whether array>array[i-k] for all k=1,2,...n/5.
I made no assumption about the data, I was just exploring the logical consequences of the problem statement.
In the case you give, the boolean is false, no further processing is required. You will hit this condition (if it is the case) in a single pass - hence O(n).
It's only interesting if the boolean is true, hence you need to keep looking. In that case the recursive analysis I posted suggests you do not need the nested loop, a single loop is sufficient, hence it runs in O(n).
I made no assumption about the data, I was just exploring the logical consequences of the problem statement.
In the case you give, the boolean is false, no further processing is required. You will hit this condition (if it is the case) in a single pass - hence O(n).
It's only interesting if the boolean is true, hence you need to keep looking. In that case the recursive analysis I posted suggests you do not need the nested loop, a single loop is sufficient, hence it runs in O(n).
Actually I made a mistaken assumption that i ∀ 0 - n. (Or i represents a range of all indices of the array).
He didn't say anything to that effect. If i is one value, then the case is trivial. If i is meant to specify a range of values, then it is impossible to do in O(n).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.