edited by
736 views
0 votes
0 votes

Argument: As it a complete tree, maximum BFS level possible are log(n). And as BFS time is O(n+E) , taking E as path cost , it will give O(n+logn) which is O(n). So, I ticked B. Answer is given as C. But, if we take a vertex just in the first level , so the time cost will be Omega(1). So, C must not be true. Where am I going wrong??

edited by

3 Answers

0 votes
0 votes
consider a binary tree in which 1,2,3,4,5,6,7 are inserted in level order.Then node 7 will be the last one to get inserted. Now we want to find the worst case search time to find 7. Consider this BFS order 1,2,3,4,5,6,7 in which we need to traverse all the 7 nodes to reach 7 i.e O(n). And the best case BFS order to find 7 is is 1,3,2,7,6,4,5 I hope this helps!
0 votes
0 votes
T is a complete binary tree so every nodes start filling from left to right so that the height of leave nodes is either at d or d-1

therfore height of the tree is log(n)

now if we follow breadth first search then we do the level order travesal so that

1st the all node at level 0 is traversed

2nd all the node at level 1 is travesed

.

.

.

till all the nodes at level nth is traversed in worst case

so from this it is clear that it depend on the height of the tree at the number of nodes

therefore , complexity will be O(nlogn)  in worst case

but in best case it will be omega(logn)
Answer:

Related questions

2 votes
2 votes
1 answer
2
3 votes
3 votes
4 answers
3
Tushar Shinde asked Jan 22, 2016
669 views
Answer is given as (B). But, shouldn't it relax point 'c' via 'a' .. So, i guess answer should be D. Is it?