dhruba.work
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Its average case is O(n). Worst case in O(n2). Being random worst case is seldom possible but for full proof Selection in worst case linear time check my comment below.
- dhruba.work March 26, 2014Comment hidden because of low score. Click to expand.
0
of 0 vote
It can be solved using medians of medians algorithm. It only gurantees O(n) worst case time complexity in ranking an element in a unsorted array. Normal Ranking algo using random pivot takes O(n2) in worst case, average case is O(n).
It can be found in Introduction to Algorithms-Cormen book in Chapter medians and Order Statistics.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
SO we need to find out the smallest positive integer that can not be formed from the sum of numbers from array​. Now from that we can infer that the number should also be not present in the array unless it is mandatory to add at least two numbers.
- dhruba.work December 11, 2014E.g. 1,2,4,8,16,32,66,69,80
Here if you see the number is 64
So going with the above assumption, we :
first will sort the array and find out the smallest missing number lets say x.
second we will get the sub set lets call it A of numbers smaller than x
perform apply the sub set sum algorithm in order to find if obtaining x is possible.
Time Complexity = Sum(x*(Number of elements in the subset A)) x start from 0 and can run till the last input in the sorted array (worst case)