# Why is the effective branching factor used for measuring performance of a heuristic function?

For search algorithms with heuristic functions, performance of heuristic functions are measured by effective branching factor $${b^*}$$ which involves total nodes expanded $${N}$$ and depth of the solution $${d}$$. I'm not able to find out how different values of $${d}$$ affect the performance keeping same $${N}$$. Put another way, why not use just the $${N}$$ as the performance measure instead of $${b^*}$$?

As you found $$N$$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $$b^*$$ for each node. In other words, the total number of nodes that are involved in the expansion process is $$N \times b^*$$.
• @ OmG - Why not ${N}$ since you agreed that the cost solely depends on ${N}$? Nov 24 '19 at 17:03
• @KGhatak because the total number of expanded node is $N \times b^*$.
• @KGhatak Unfortunately I don't know which part is confusing for you. In the search, we expand $N$ nodes, and each node has $b^*$ children at most. Hence, the complexity is related to $N$ and $b^*$. Now, suppose we do not apply $b^*$ in the complexity, and another algorithm try to search and expand $N$ nodes to find the solution, but the branching factor of the current algorithm would be $2^{b^*}$! Which of them will be a better algorithm in terms of complexity?
• @ OmG - Let me put it in a different way. Two algorithms, say 1 and 2, try to solve a problem. Their respective values are ${N_1}, {b_1^*}, {N_2}$, and ${b_2^*}$ such that ${N_1b_1^*}={N_2b_2^*}$. Which algorithm is efficient given ${N_1>N_2}$. Would you pls explain! Nov 25 '19 at 18:26