|
5 Jan 2004, 13:23
|
#1
|
Born Sinful
Join Date: Nov 2000
Location: Loughborough, UK
Posts: 4,059
|
Search complexity
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.
__________________
Worth dying for. Worth killing for. Worth going to hell for. Amen.
|
|
|
5 Jan 2004, 16:37
|
#2
|
Spelling is for pussies
Join Date: Mar 2003
Location: Actually, where the feck am I........?
Posts: 446
|
Re: Search complexity
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....?
__________________
If God made me in his image, he's one fat ugly biatch.
I always get the soggy biscuit
Veni Vidi Codi
|
|
|
5 Jan 2004, 17:29
|
#3
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Re: Search complexity
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.
Last edited by queball; 5 Jan 2004 at 17:47.
|
|
|
5 Jan 2004, 21:19
|
#4
|
Born Sinful
Join Date: Nov 2000
Location: Loughborough, UK
Posts: 4,059
|
Re: Search complexity
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.
__________________
Worth dying for. Worth killing for. Worth going to hell for. Amen.
|
|
|
5 Jan 2004, 22:01
|
#5
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Re: Search complexity
Quote:
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.
__________________
Gubble gubble gubble gubble
|
|
|
6 Jan 2004, 15:14
|
#6
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Re: Search complexity
Quote:
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)
Quote:
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.
|
|
|
6 Jan 2004, 19:45
|
#7
|
Love's Sweet Exile
Join Date: May 2001
Location: Living on a Stair (Now Sword-less)
Posts: 2,371
|
Re: Search complexity
Isn't that what the Principle of Invariance is all about?
__________________
--SYMM--
Ba Ba Ti Ki Di Do
|
|
|
7 Jan 2004, 19:28
|
#8
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Re: Search complexity
Quote:
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.
__________________
Gubble gubble gubble gubble
|
|
|
|
All times are GMT +1. The time now is 19:17.
| |