Majority Element

Majority Element Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows: I/P : 3

Read More

Pseudo-polynomial Algorithms

Pseudo-polynomial Algorithms What is Pseudo-polynomial? An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo-polynomial algorithm. For example, consider the problem of counting frequencies of all elements in an array of positive numbers. A pseudo-polynomial time solution for this is to first find the maximum

Read More

What does ‘Space Complexity’ mean?

What does ‘Space Complexity’ mean? Space Complexity: The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity. Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm

Read More