The time and space complexity of BFS is (For time and space complexity problems consider b as branching factor and d as depth of the search tree.) a) O(bd+1) and O(bd+1) b) O(b2) and O(d2) c) O(d2) and O(b2) d) O(d2) and O(d2)

The time and space complexity of BFS is (For time and space complexity problems consider b as

branching factor and d as depth of the search tree.)

a) O(bd+1) and O(bd+1)

b) O(b2) and O(d2)

c) O(d2) and O(b2)

d) O(d2) and O(d2)
by

1 Answer

Answer :

a) O(bd+1) and O(bd+1)
by

Related questions

What is the space complexity of Depth-first search? a) O(b) b) O(bl) c) O(m) d) O(bm)

Description : What is the space complexity of Depth-first search? a) O(b) b) O(bl) c) O(m) d) O(bm)

Last Answer : d) O(bm)

Write the time & space complexity associated with depth limited search.

Description : Write the time & space complexity associated with depth limited search.

Last Answer : Time complexity =O (bd) ,  b-branching factor,  d-depth of tree Space complexity=o (bl)

Which of the following is/are Uninformed Search technique/techniques? a) Breadth First Search (BFS) b) Depth First Search (DFS) c) Bidirectional Search d) All of the mentioned

Description : Which of the following is/are Uninformed Search technique/techniques? a) Breadth First Search (BFS) b) Depth First Search (DFS) c) Bidirectional Search d) All of the mentioned

Last Answer : d) All of the mentioned

Which is true regarding BFS (Breadth First Search)? a) BFS will get trapped exploring a single path b) The entire tree so far been generated must be stored in BFS c) BFS is not guaranteed to find a solution if exists d) BFS is nothing but Binary First Search

Description : Which is true regarding BFS (Breadth First Search)? a) BFS will get trapped exploring a single path b) The entire tree so far been generated must be stored in BFS c) BFS is not guaranteed to find a solution if exists d) BFS is nothing but Binary First Search

Last Answer : b) The entire tree so far been generated must be stored in BFS

General algorithm applied on game tree for making decision of win/lose is ____________ a) DFS/BFS Search Algorithms b) Heuristic Search Algorithms c) Greedy Search Algorithms d) MIN/MAX Algorithms

Description : General algorithm applied on game tree for making decision of win/lose is ____________ a) DFS/BFS Search Algorithms b) Heuristic Search Algorithms c) Greedy Search Algorithms d) MIN/MAX Algorithms

Last Answer : d) MIN/MAX Algorithms

DFS is ______ efficient and BFS is __________ efficient. a) Space, Time b) Time, Space c) Time, Time d) Space, Space

Description : DFS is ______ efficient and BFS is __________ efficient. a) Space, Time b) Time, Space c) Time, Time d) Space, Space

Last Answer : a) Space, Time

The main idea of Bidirectional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node. a) True b) False

Description : The main idea of Bidirectional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node. a) True b) False

Last Answer : a) True

Define Branching factor b*.

Description : Define Branching factor b*.

Last Answer : Uniform tree of depth d would have to be in order to contain N+1 nodes is called branching factor. 

Define branching factor (b).

Description : Define branching factor (b).

Last Answer : The number of nodes which is connected to each of the node in search tree is called Branching factor. 

Which of the following search belongs to totally ordered plan search? a) Forward state-space search b) Hill-climbing search c) Depth-first search d) Breadth-first search

Description : Which of the following search belongs to totally ordered plan search? a) Forward state-space search b) Hill-climbing search c) Depth-first search d) Breadth-first search

Last Answer : a) Forward state-space search

Which is the most straightforward approach for planning algorithm? a) Best-first search b) State-space search c) Depth-first search d) Hill-climbing search

Description : Which is the most straightforward approach for planning algorithm? a) Best-first search b) State-space search c) Depth-first search d) Hill-climbing search

Last Answer : b) State-space search

Which method is used to search better by learning? a) Best-first search b) Depth-first search c) Metalevel state space d) None of the mentioned

Description : Which method is used to search better by learning? a) Best-first search b) Depth-first search c) Metalevel state space d) None of the mentioned

Last Answer : c) Metalevel state space

Which search uses only the linear space for searching? a) Best-first search b) Recursive best-first search c) Depth-first search d) None of the mentioned

Description : Which search uses only the linear space for searching? a) Best-first search b) Recursive best-first search c) Depth-first search d) None of the mentioned

Last Answer : b) Recursive best-first search

What is the major component/components for measuring the performance of problem solving? a) Completeness b) Optimality c) Time and Space complexity d) All of the mentioned

Description : What is the major component/components for measuring the performance of problem solving? a) Completeness b) Optimality c) Time and Space complexity d) All of the mentioned

Last Answer : d) All of the mentioned

Depth-first search always expands the ______ node in the current fringe of the search tree. a) Shallowest b) Child node c) Deepest d) Minimum cost

Description : Depth-first search always expands the ______ node in the current fringe of the search tree. a) Shallowest b) Child node c) Deepest d) Minimum cost

Last Answer : c) Deepest

_____________ algorithms is used to extract the plan directly from the planning graph, rather than using graph to provide heuristic. a) BFS/DFS b) A* c) Graph-Plan d) Greedy

Description : _____________ algorithms is used to extract the plan directly from the planning graph, rather than using graph to provide heuristic. a) BFS/DFS b) A* c) Graph-Plan d) Greedy

Last Answer : c) Graph-Plan

Optimality of BFS is ___________ a) When there is less number of nodes b) When all step costs are equal c) When all step costs are unequal d) None of the mentioned

Description : Optimality of BFS is ___________ a) When there is less number of nodes b) When all step costs are equal c) When all step costs are unequal d) None of the mentioned

Last Answer : b) When all step costs are equal

Which data structure conveniently used to implement BFS? a) Stacks b) Queues c) Priority Queues d) All of the mentioned

Description : Which data structure conveniently used to implement BFS? a) Stacks b) Queues c) Priority Queues d) All of the mentioned

Last Answer : b) Queues

Differentiate BFS & DFS.

Description : Differentiate BFS & DFS.

Last Answer : BFS means breath wise search. Space complexity is more. Do not give optimal solution Queuing fn is same as that of queue operator DFS means depth wise search. Space complexity is less Gives optimal solution Queuing fn is somewhat different from queue operator.

hydraulically equivalent, the relationship which holds good, is A. D8/3 = 4 b8/3 B. D3/8 = 4 b3/8 C. D2/3 = 4 b2/3 D. D3/2 = 4 b3/2

Description : hydraulically equivalent, the relationship which holds good, is A. D8/3 = 4 b8/3 B. D3/8 = 4 b3/8 C. D2/3 = 4 b2/3 D. D3/2 = 4 b3/2

Last Answer : ANS: A

The initial state and the legal moves for each side define the __________ for the game. a) Search Tree b) Game Tree c) State Space Search d) Forest

Description :  The initial state and the legal moves for each side define the __________ for the game. a) Search Tree b) Game Tree c) State Space Search d) Forest

Last Answer : b) Game Tree

The term ___________ is used for a depth-first search that chooses values for one variable at a time and returns when a variable has no legal values left to assign. a) Forward search b) Backtrack search c) Hill algorithm d) Reverse-Down-Hill search

Description : The term ___________ is used for a depth-first search that chooses values for one variable at a time and returns when a variable has no legal values left to assign. a) Forward search b) Backtrack search c) Hill algorithm d) Reverse-Down-Hill search

Last Answer : b) Backtrack search

Which algorithm is used for solving temporal probabilistic reasoning? a) Hill-climbing search b) Hidden markov model c) Depth-first search d) Breadth-first search

Description : Which algorithm is used for solving temporal probabilistic reasoning? a) Hill-climbing search b) Hidden markov model c) Depth-first search d) Breadth-first search

Last Answer : b) Hidden markov model

Which algorithm takes two sentences and returns a unifier? a) Inference b) Hill-climbing search c) Depth-first search d) Unify algorithm

Description : Which algorithm takes two sentences and returns a unifier? a) Inference b) Hill-climbing search c) Depth-first search d) Unify algorithm

Last Answer : d) Unify algorithm

Which algorithm are in more similar to backward chaining algorithm? a) Depth-first search algorithm b) Breadth-first search algorithm c) Hill-climbing search algorithm d) All of the mentioned

Description : Which algorithm are in more similar to backward chaining algorithm? a) Depth-first search algorithm b) Breadth-first search algorithm c) Hill-climbing search algorithm d) All of the mentioned

Last Answer : a) Depth-first search algorithm

Which search is similar to minimax search? a) Hill-climbing search b) Depth-first search c) Breadth-first search d) All of the mentioned

Description : Which search is similar to minimax search? a) Hill-climbing search b) Depth-first search c) Breadth-first search d) All of the mentioned

Last Answer : b) Depth-first search

Which search is equal to minimax search but eliminates the branches that can’t influence the final decision? a) Depth-first search b) Breadth-first search c) Alpha-beta pruning d) None of the mentioned

Description : Which search is equal to minimax search but eliminates the branches that can’t influence the final decision? a) Depth-first search b) Breadth-first search c) Alpha-beta pruning d) None of the mentioned

Last Answer : c) Alpha-beta pruning

Which of the following algorithm is generally used CSP search algorithm? a) Breadth-first search algorithm b) Depth-first search algorithm c) Hill-climbing search algorithm d) None of the mentioned

Description : Which of the following algorithm is generally used CSP search algorithm? a) Breadth-first search algorithm b) Depth-first search algorithm c) Hill-climbing search algorithm d) None of the mentioned

Last Answer : b) Depth-first search algorithm

A* algorithm is based on ___________ a) Breadth-First-Search b) Depth-First –Search c) Best-First-Search d) Hill climbing

Description : A* algorithm is based on ___________ a) Breadth-First-Search b) Depth-First –Search c) Best-First-Search d) Hill climbing

Last Answer : c) Best-First-Search

Which search is complete and optimal when h(n) is consistent? a) Best-first search b) Depth-first search c) Both Best-first & Depth-first search d) A* search

Description : Which search is complete and optimal when h(n) is consistent? a) Best-first search b) Depth-first search c) Both Best-first & Depth-first search d) A* search

Last Answer : d) A* search

Which function will select the lowest expansion node at first for evaluation? a) Greedy best-first search b) Best-first search c) Depth-first search d) None of the mentioned

Description : Which function will select the lowest expansion node at first for evaluation? a) Greedy best-first search b) Best-first search c) Depth-first search d) None of the mentioned

Last Answer : b) Best-first search

Which search uses the problem specific knowledge beyond the definition of the problem? a) Informed search b) Depth-first search c) Breadth-first search d) Uninformed search

Description : Which search uses the problem specific knowledge beyond the definition of the problem? a) Informed search b) Depth-first search c) Breadth-first search d) Uninformed search

Last Answer : a) Informed search

Which search implements stack operation for searching the states? a) Depth-limited search b) Depth-first search c) Breadth-first search d) None of the mentioned

Description : Which search implements stack operation for searching the states? a) Depth-limited search b) Depth-first search c) Breadth-first search d) None of the mentioned

Last Answer : b) Depth-first search

Which search algorithm imposes a fixed depth limit on nodes? a) Depth-limited search b) Depth-first search c) Iterative deepening search d) Bidirectional search

Description : Which search algorithm imposes a fixed depth limit on nodes? a) Depth-limited search b) Depth-first search c) Iterative deepening search d) Bidirectional search

Last Answer : a) Depth-limited search

Which search is implemented with an empty first-in-first-out queue? a) Depth-first search b) Breadth-first search c) Bidirectional search d) None of the mentioned

Description : Which search is implemented with an empty first-in-first-out queue? a) Depth-first search b) Breadth-first search c) Bidirectional search d) None of the mentioned

Last Answer : b) Breadth-first search

Which search method takes less memory? a) Depth-First Search b) Breadth-First search c) Linear Search d) Optimal search

Description : Which search method takes less memory? a) Depth-First Search b) Breadth-First search c) Linear Search d) Optimal search

Last Answer : a) Depth-First Search

The _______ is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. a) Finding shortest path between a source and a destination b) Travelling Salesman problem c) Map coloring problem d) Depth first search traversal on a given map represented as a graph

Description : The _______ is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. a) Finding shortest path between a source and a destination b) Travelling ... c) Map coloring problem d) Depth first search traversal on a given map represented as a graph

Last Answer : b) Travelling Salesman problem

Which search agent operates by interleaving computation and action? a) Offline search b) Online search c) Breadth-first search d) Depth-first search

Description : Which search agent operates by interleaving computation and action? a) Offline search b) Online search c) Breadth-first search d) Depth-first search

Last Answer : b) Online search

Which search method takes less memory? a) Depth-First Search b) Breadth-First search c) Optimal search d) Linear Search

Description : Which search method takes less memory? a) Depth-First Search b) Breadth-First search c) Optimal search d) Linear Search

Last Answer : a) Depth-First Search

Define depth limited search.

Description : Define depth limited search.

Last Answer : The problem of unbounded tress can be avoided by supplying depth limit 1(i.e.) nodes at depth 1 are treated as if they have no successors. This is called Depth Limited search. 

Define Depth first search.

Description : Define Depth first search.

Last Answer :  It expands the deepest node in the current fringe of the search tree.  

State True or False. i) Binary search is used for searching in a sorted array. ii) The time complexity of binary search is O(logn). A) True, False B) False, True C) False, False D) True, True

Description : State True or False. i) Binary search is used for searching in a sorted array. ii) The time complexity of binary search is O(logn). A) True, False B) False, True C) False, False D) True, True

Last Answer : D) True, True

Match the following. a) Completeness i) How long does it take to find a solution b) Time Complexity ii) How much memory need to perform the search. c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one. A) a-iii, b-ii, c-i B) a-i, b-ii, c-iii C) a-iii, b-i, c-ii D) a-i, b-iii, c-ii

Description : Match the following. a) Completeness i) How long does it take to find a solution b) Time Complexity ii) How much memory need to perform the search. c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in ... , b-ii, c-iii C) a-iii, b-i, c-ii D) a-i, b-iii, c-ii

Last Answer : C) a-iii, b-i, c-ii

Computational learning theory analyzes the sample complexity and computational complexity of __________ a) Unsupervised Learning b) Inductive learning c) Forced based learning d) Weak learning

Description : Computational learning theory analyzes the sample complexity and computational complexity of __________ a) Unsupervised Learning b) Inductive learning c) Forced based learning d) Weak learning

Last Answer : b) Inductive learning

Which makes the complexity of the entire algorithm quadratic in the size? a) Clause b) Inference c) Resolution d) Occur check

Description : Which makes the complexity of the entire algorithm quadratic in the size? a) Clause b) Inference c) Resolution d) Occur check

Last Answer : d) Occur check

Which problem can frequently occur in backward chaining algorithm? a) Repeated states b) Incompleteness c) Complexity d) Both Repeated states & Incompleteness

Description : Which problem can frequently occur in backward chaining algorithm? a) Repeated states b) Incompleteness c) Complexity d) Both Repeated states & Incompleteness

Last Answer : d) Both Repeated states & Incompleteness

How many possible sources of complexity are there in forward chaining? a) 1 b) 2 c) 3 d) 4

Description : How many possible sources of complexity are there in forward chaining? a) 1 b) 2 c) 3 d) 4

Last Answer : c) 3

Which will solve the conjuncts of the rule so that the total cost is minimized? a) Constraint variable b) Conjunct ordering c) Data complexity d) All of the mentioned

Description : Which will solve the conjuncts of the rule so that the total cost is minimized? a) Constraint variable b) Conjunct ordering c) Data complexity d) All of the mentioned

Last Answer : b) Conjunct ordering

n(log n) is referred to A. A measure of the desired maximal complexity of data mining algorithms B. A database containing volatile data used for the daily operation of an organization C. Relational database management system D. None of these

Description : n(log n) is referred to A. A measure of the desired maximal complexity of data mining algorithms B. A database containing volatile data used for the daily operation of an organization C. Relational database management system D. None of these

Last Answer : A. A measure of the desired maximal complexity of data mining algorithms

Computational learning theory analyzes the sample complexity and computational complexity of a) Unsupervised Learning b) Inductive learning c) Forced based learning d) Weak learning e) Knowledge based learning

Description : Computational learning theory analyzes the sample complexity and computational complexity of a) Unsupervised Learning b) Inductive learning c) Forced based learning d) Weak learning e) Knowledge based learning

Last Answer : b) Inductive learning