GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
281 views

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)

asked in Algorithms by Active (1.2k points)   | 281 views

2 Answers

+1 vote

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 :

 

answered by Veteran (23.2k points)  
edited by
We have been given an array of $N$ numbers, hence, we will always end up in making Balanced BST, so we can say $O(NlogN)$ .

http://gateoverflow.in/50681/time-complexity-of-binary-tree-and-bst

 

@Kapil this should be wrong rt ??

because if array is sorted than we can find middle .... 

For Sorted Array complexity to build BST will be O(n) 

@Gabbar, for a BST like this,

at max we would go till the height of the tree right? which would take O(log n) and we need to do this for all the elements, so, O(n log n) right?

Can you please clarify?

It is directly given array so we can sort it...

Sorted array ....to build Bst of sorted array ...

T(n) = 2 T(n/2) + c
But TC of building a BST is O(n log n) right?
@Gabbar

Question says only array not sorted array, rt ?

With only array, array is first sorted then can be made BST, but here augmented BST with extra space is needed, so TC = O(NLogN + N)
so its O(n log n) right?
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..

answered by Veteran (68.7k points)  

@Habib Just one doubt : We are given array of numbers [may be sorted not always] so to apply inorder traversal first we need to build the BST so T.C can never be less than nlogn right ?

Time for max : Build BSt with augmentation + Inorder Traversal = O(nlogn) + O(n) ==> O(nlogn)

Sir, for checking whether the key is already present in BST would take log n time right? and doing this for n items would take n log n right?
Here my point is : We can make the binary search tree augmented as I described by taking care in insertion itself so that we can solve the problem of finding frequent element in O(n) time..We take care of that fact in insertion itself..
Sir, so finding the element with max frequency element will take O(n) if we don't consider insertion cost right?

If so, why shouldn't we consider it?

@Gate Mission 1, A tree traversal would take only O(n) because all tree tranversals are depth first traversals, tc of dfs is O(n+m) $\simeq$ O(n). In another way we visit all the n nodes, so O(n).

@habib your approach is correct all is you are not thinking of worst case of BST on each insert if you first find nd then decide whether to insert or not --> Aren't you going to include time for "finding" --> consider skew bst. only finding time leads to triangle numbers.

@nitish don't complicate that much, tree traversal means exploring edges and in any traversal you can traverse an edges at most twice (once exploring and once backtracking) and in tree there are n-1 edges so T.C is always O(n).

Yeah @Gate Mission 1 that is what I meant.

What I don't understand is why we should ignore insertion cost?



Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users