recategorized by
2,086 views
3 votes
3 votes
Consider an array with ‘n’ numbers, let “T” be time complexity for finding a number appeared maximum number of times in an array. Using Binary Search Tree data structure the T will be

A. O(log n)

B. O(n)

C. O(n logn)

D. O(n2)
recategorized by

2 Answers

1 votes
1 votes

Suppose number is given x we need to find it appears maximum number of times or not i.e more than n/2 times or not.

Array is not give in sorted order So use Inoredr Traversal and sort it O(n). Logic over here is find the index of x into the array by using Binary search O(logn) time suppose index is i. Now check element at (i + n/2) =O(1) also x if yes than it is maximal element else not. 

If Array has given in sorted order than Time complexity will be O(logn) but Here  O(n). 

Assuming BST available. If not available than O(nlogn) should be the ans 

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Same procedure apply for when x is not given .

Step1: Build BST= O(nlogn)  = Sort the array + Than build BST  = O( nlogn + n )

Step2. Each Element search into BST and check it's index i and i+ (n/2)th element = O(nlogn)

So Time complexity = O(nlogn)

----------------------------------------------------------------------------------------------------------------------------------------------------------------

Improvement Welcomes :

edited by
0 votes
0 votes

Using augmentation in binary search tree , we can simplify this problem..

So what we do is we modify in insertion method..First prior to insertion if we find the key already is present in BST then we increase the count field of the concerned node..

Else we insert the node and make count of it = 1 in the augmented BST..

So to find maximum frequency character we do inorder traversal of this BST and check the count value and update the max value and character as and when required..

Hence the complexity is O(n)..Hence B) should be correct answer..

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
pradeepchaudhary asked Aug 19, 2018
19,106 views
8. What are the worst case and average case complexities of a binary search tree?a) O(n), O(n)b) O(logn), O(logn)c) O(logn), O(n)d) O(n), O(logn)
5 votes
5 votes
1 answer
3
VS asked Jan 14, 2018
929 views
A balanced binary search tree of n nodes,the number of steps needed to find and remove the 9th largest element in the worst case?(Please mention the algorithm followed)