Search complexity

[meglamaniac]

Ok, this isn't actually programming related but I figured someone on here probably knows.

Some of my AI notes I'm reading up on have confused me, and I suspect it's cos I copied them down wrong. The section that's got me going "eh?" is related to a bi-directional search.
The note in question is:

* If branching factor is b in both directions (this is best case scenario for implementation) and shallowest solution is at depth d, then Space and Time complexities are both:
O(2b^(d/2)) = O(b^(d/2))

How can they both be equal? Have I just forgotten how big O notation works (very probable), have I written nonsense, or is it a combination of both? I can't remember this lecture AT ALL and my mate can't find her notes for it either (a right pair WE are).

Ta.

[SbOlly]

O(2b^(d/2)) = O(b^(d/2))

Ok, I'm going to jump in without reading the question first, but aren't they not equal because of the 2? Or something....?

[queball]

O(2) = O(1). Big-O notation ignores coefficients. Go back to your definitions.

do you mean how can space and time complexity be equal? blah, I'll have to actually get a pen and paper for that one. basically because you're exploring a tree, and keeping it in memory, so the memory and time used are similar.

[meglamaniac]

No, nothing that complex (in fact I more or less get that).
I've just completely lost track of how to "do" Big-O and the definitions are the other thing I can't find heh.

Is O(2b^(d/2) meant to be read, in strict terms, as O(2(b^(d/2)))?
If so I can see why we lose the 2, if not I need to hunt down those definitions I think.

[W]

Originally Posted by meglamaniac

No, nothing that complex (in fact I more or less get that).
I've just completely lost track of how to "do" Big-O and the definitions are the other thing I can't find heh.

Is O(2b^(d/2) meant to be read, in strict terms, as O(2(b^(d/2)))?
If so I can see why we lose the 2, if not I need to hunt down those definitions I think.

It makes a difference whether both b and d are dimensions of the task or if just one of them is. If both are, O(2b^(d/2)) is the same as O(b^d) no matter what.

Each dimension, and the end result, can each be multiplied by an arbitrary constant.

[queball]

Originally Posted by meglamaniac

Is O(2b^(d/2) meant to be read, in strict terms, as O(2(b^(d/2)))?

Yes. (Unless you got the formula wrong and have weird notation)

Originally Posted by W

It makes a difference whether both b and d are dimensions of the task or if just one of them is. If both are, O(2b^(d/2)) is the same as O(b^d) no matter what.

Each dimension, and the end result, can each be multiplied by an arbitrary constant.

I haven't seen a convention where the dimensions can be multiplied by arbitrary constants.

[SYMM]

Isn't that what the Principle of Invariance is all about?

[W]

Originally Posted by queball

I haven't seen a convention where the dimensions can be multiplied by arbitrary constants.

I'm sure I've thrown away my textbook on algoritm analysis by now, but I remember it containing the proof of this.