Yioop - PHP Search Engine

Feb 17 In-Class Exercise Thread.

Please post your solutions to the Feb 17 In-Class Exercise to this thread.

Best,

Chris

Please post your solutions to the Feb 17 In-Class Exercise to this thread. Best, Chris

-- Feb 17 In-Class Exercise Thread

Formulae:

binary search: O (n * l * log(L))
sequential search: O (n * L)
galloping search: O (n * l * (1+log(L/l)))

In this example, n = 2 since we have "two-term queries". f will replace l, and L will be replaced by f * whatever coefficient depending on the case

Case 1:

binary search: O (2 * f * log 1f) = O (2f log f)
sequential search: O (2 * 1f) = O (2f)
galloping search: O (2 * f * (1 + log(1f/f))) = O (2 * f) = O (2f)

Case 2:

binary search: O (2 * f * log 2f) = O (2f log 2f) = O (2f (log f + log 2)) = O (2f + 2flog f))
sequential search: O (2 * 2f) = O (4f)
galloping search: O (2 * f * (1 + log(2f/f))) = O (2 * 2f) = O (4f)

Case 3:

binary search: O (2 * f * log 4f) = O (2f log 4f) = O (2f (log f + log 4)) = O (4f + 2flog f))
sequential search: O (2 * 4f) = O (8f)
galloping search: O (2 * f * (1 + log(4f/f))) = O (2 * 3f) = O (6f)

Case 4:

binary search: O (2 * f * log 8f) = O (2f log 8f) = O (2f (log f + log 8)) = O (6f + 2flog f))
sequential search: O (2 * 8f) = O (16f)
galloping search: O (2 * f * (1 + log(8f/f))) = O (2 * 4f) = O (8f)

(Edited: 2021-02-17)

Formulae: * binary search: O (n * l * log(L)) * sequential search: O (n * L) * galloping search: O (n * l * (1+log(L/l))) In this example, n = 2 since we have "two-term queries". f will replace l, and L will be replaced by f * whatever coefficient depending on the case Case 1: * binary search: O (2 * f * log 1f) = O (2f log f) * sequential search: O (2 * 1f) = O (2f) * galloping search: O (2 * f * (1 + log(1f/f))) = O (2 * f) = O (2f) Case 2: * binary search: O (2 * f * log 2f) = O (2f log 2f) = O (2f (log f + log 2)) = O (2f + 2flog f)) * sequential search: O (2 * 2f) = O (4f) * galloping search: O (2 * f * (1 + log(2f/f))) = O (2 * 2f) = O (4f) Case 3: * binary search: O (2 * f * log 4f) = O (2f log 4f) = O (2f (log f + log 4)) = O (4f + 2flog f)) * sequential search: O (2 * 4f) = O (8f) * galloping search: O (2 * f * (1 + log(4f/f))) = O (2 * 3f) = O (6f) Case 4: * binary search: O (2 * f * log 8f) = O (2f log 8f) = O (2f (log f + log 8)) = O (6f + 2flog f)) * sequential search: O (2 * 8f) = O (16f) * galloping search: O (2 * f * (1 + log(8f/f))) = O (2 * 4f) = O (8f)

-- Feb 17 In-Class Exercise Thread

l = f; n = 2

Case 1: L = f
Binary Search
O(2flog(f))

Sequential Search
O(2f)

Galloping Search
O(nflog(1 + log(f/f))) = O(nf) = O(2f)
Case 2: L = 2f
Binary Search
O(nf*log(2f)) = O(nf(log(f) + log2)) = O(2f(log(f) + 1))

Sequential Search
O(4f)

Galloping Search
O(nflog(1 + log(2f/f))) = O(4f)
Case 3: L = 4f
Binary Search
O(nf*log(4f)) = O(nf(log(f) + 2log2)) = O(2f(log(f) + 2))

Sequential Search
O(8f)

Galloping Search
O(nflog(1 + log(4f/f))) = O(6f)
Case 4: L = 8f
Binary Search
O(nf*log(2f)) = O(nf(log(f) + 4log2)) = O(2f(log(f) + 4))

Sequential Search
O(16f)

Galloping Search
O(nflog(1 + log(8f/f))) = O(8f)

(Edited: 2021-02-17)

l = f; n = 2 *Case 1: L = f ;Binary Search: O(2flog(f)) ;Sequential Search: O(2f) ;Galloping Search: O(nflog(1 + log(f/f))) = O(nf) = O(2f) *Case 2: L = 2f ;Binary Search: O(nf*log(2f)) = O(nf(log(f) + log2)) = O(2f(log(f) + 1)) ;Sequential Search: O(4f) ;Galloping Search: O(nflog(1 + log(2f/f))) = O(4f) *Case 3: L = 4f ;Binary Search: O(nf*log(4f)) = O(nf(log(f) + 2log2)) = O(2f(log(f) + 2)) ;Sequential Search: O(8f) ;Galloping Search: O(nflog(1 + log(4f/f))) = O(6f) *Case 4: L = 8f ;Binary Search: O(nf*log(2f)) = O(nf(log(f) + 4log2)) = O(2f(log(f) + 4)) ;Sequential Search: O(16f) ;Galloping Search: O(nflog(1 + log(8f/f))) = O(8f)

-- Feb 17 In-Class Exercise Thread

L = 1f Case 1 ---

          binary search     : O(2*f*logf) 
          Sequential search : O(2*f)
          Galloping search  : O(2*f*(1+log(f/f)) 
                               = O(2*f)

L = 2f Case 2 ---

          binary search    : O(2*f*log2f) 
                            = O(2*f*(logf+log2)) 
                            = O((2*f*logf)+(2*f))
          Sequential search : O(2*2f) 
                             = O(4*f)
          Galloping search : O(2*f*(1+log(2f/f)) 
                             = O(4*f)

L = 4f Case 3 ---

          binary search : O(2*f*log4f) 
                        = O(2*f*(logf+log4)) 
                        = O((2*f*logf)+(4*f))
          Sequential search : O(2*4f) 
                            = O(8*f)
          Galloping search : O(2*f*(1+log(4f/f))
                            = O(6*f)

L = 8f Case 4 ---

          binary search : O(2*f*log8f) 
                         = O(2*f*(logf+log8))
                         = O((2*f*logf)+(6*f))
          Sequential search : O(2*8f) 
                            = O(16*f)
          Galloping search : O(2*f*(1+log(8f/f)) 
                            = O(8*f)

(Edited: 2021-02-17)

L = 1f Case 1 --- binary search : O(2*f*logf) Sequential search : O(2*f) Galloping search : O(2*f*(1+log(f/f)) = O(2*f) L = 2f Case 2 --- binary search : O(2*f*log2f) = O(2*f*(logf+log2)) = O((2*f*logf)+(2*f)) Sequential search : O(2*2f) = O(4*f) Galloping search : O(2*f*(1+log(2f/f)) = O(4*f) L = 4f Case 3 --- binary search : O(2*f*log4f) = O(2*f*(logf+log4)) = O((2*f*logf)+(4*f)) Sequential search : O(2*4f) = O(8*f) Galloping search : O(2*f*(1+log(4f/f)) = O(6*f) L = 8f Case 4 --- binary search : O(2*f*log8f) = O(2*f*(logf+log8)) = O((2*f*logf)+(6*f)) Sequential search : O(2*8f) = O(16*f) Galloping search : O(2*f*(1+log(8f/f)) = O(8*f)

-- Feb 17 In-Class Exercise Thread

 Linear => 2*l, 4*l, 8*l, 16*l
 Binary => 2*l*log(l), 2*l*log(l)+2l, 2*l*log(l)+4l, 2*l*log(l)+6l
 Galloping => 2*l, 4*l, 6*l, 8*l

(Edited: 2021-02-17)

Linear => 2*l, 4*l, 8*l, 16*l Binary => 2*l*log(l), 2*l*log(l)+2l, 2*l*log(l)+4l, 2*l*log(l)+6l Galloping => 2*l, 4*l, 6*l, 8*l

-- Feb 17 In-Class Exercise Thread

case 1: L = l

binary search: O(2l*log(l))
sequential: O(2l)
galloping: O(2l)

case 2: L = 2l

binary search: O(2l*log(l) + 2l)
sequential: O(4l)
galloping: O(4l)

case 3: L = 4l

binary search: O(2l*log(l) + 4l)
sequential: O(8l)
galloping: O(6l)

case 4: L = 8l

binary search: O(2l*log(l) + 6l)
sequential: O(16l)
galloping: O(8l)

(Edited: 2021-02-17)

case 1: L = l * binary search: O(2l*log(l)) * sequential: O(2l) * galloping: O(2l) case 2: L = 2l *binary search: O(2l*log(l) + 2l) *sequential: O(4l) *galloping: O(4l) case 3: L = 4l *binary search: O(2l*log(l) + 4l) *sequential: O(8l) *galloping: O(6l) case 4: L = 8l *binary search: O(2l*log(l) + 6l) *sequential: O(16l) *galloping: O(8l)

-- Feb 17 In-Class Exercise Thread

n = 2

Case 1 (l, l)

Binary search: O(2 * l * log (l))
Sequential search: O(2 * l)
Galloping search: O(2 * l * (log(l/l) + 1)) = O(2 * l)

Case 2 (l, 2 * l)

Binary search: O(2 * l * log (2 * l)) = O(2 * l * log l + 2 * l)
Sequential search: O(2 * 2 * l) = O(4 * l)
Galloping search: O(2 * l * (log(2l/l) + 1)) = O(2 * l * 2) = O(4 * l)

Case 3 (l, 4 * l)

Binary search: O(2 * l * log (4 * l)) = O(2 * l * log l + 4 * l)
Sequential search: O(2 * 4 * l) = O(8 * l)
Galloping search: O(2 * l * (log(4l/l) + 1)) = O(2 * l * 3) = O(6 * l)

Case 4 (l, 8 * l)

Binary search: O(2 * l * log (8 * l)) = O(2 * l * log l + 6 * l)
Sequential search: O(2 * 8 * l) = O(16 * l)
Galloping search: O(2 * l * (log(8l/l) + 1)) = O(2 * l * 4) = O(8 * l)

n = 2 Case 1 (l, l) * Binary search: O(2 * l * log (l)) * Sequential search: O(2 * l) * Galloping search: O(2 * l * (log(l/l) + 1)) = O(2 * l) Case 2 (l, 2 * l) * Binary search: O(2 * l * log (2 * l)) = O(2 * l * log l + 2 * l) * Sequential search: O(2 * 2 * l) = O(4 * l) * Galloping search: O(2 * l * (log(2l/l) + 1)) = O(2 * l * 2) = O(4 * l) Case 3 (l, 4 * l) * Binary search: O(2 * l * log (4 * l)) = O(2 * l * log l + 4 * l) * Sequential search: O(2 * 4 * l) = O(8 * l) * Galloping search: O(2 * l * (log(4l/l) + 1)) = O(2 * l * 3) = O(6 * l) Case 4 (l, 8 * l) * Binary search: O(2 * l * log (8 * l)) = O(2 * l * log l + 6 * l) * Sequential search: O(2 * 8 * l) = O(16 * l) * Galloping search: O(2 * l * (log(8l/l) + 1)) = O(2 * l * 4) = O(8 * l)

-- Feb 17 In-Class Exercise Thread

General:

binary search: O(n * l * log L)
sequential search: O(n * L)
galloping search: O[n * l * (log (L/l) + 1)]

n = 2, l = f

L = f:

binary: O(2f log f)
sequential: O(2f)
galloping: O(2f)

L = 2f

binary: O(2f log2f) = O(2f + 2f log f)
sequential: O(4f)
galloping: O(2f * (log 2 + 1) = O(4f)

L = 4f

binary: O(2f * log 4f) = O(2f * log 4 + 2f * log f) = O(4f + 2f log f)
sequential: O(2*4f) = O(8f)
galloping: = O(2f * (log 4 + 1)) = O(6f)

L = 8f

binary: O(2f * log 8f) = O(2f log 8 + 2f log f) = O(6f + 2f log f)
sequential: O(16f)
galloping: O(2f * (log 8 + 1)) = O(2f * 4) = O(8f)

(Edited: 2021-02-17)

'''General:''' *'''binary search:''' O(n * l * log L) *'''sequential search:''' O(n * L) *'''galloping search:''' O[n * l * (log (L/l) + 1)] '''n = 2, l = f''' '''L = f:''' *binary: '''O(2f log f)''' *sequential: '''O(2f)''' *galloping: '''O(2f)''' '''L = 2f''' *binary: O(2f log2f) = '''O(2f + 2f log f)''' *sequential: '''O(4f)''' *galloping: O(2f * (log 2 + 1) = '''O(4f)''' '''L = 4f''' *binary: O(2f * log 4f) = O(2f * log 4 + 2f * log f) = '''O(4f + 2f log f)''' *sequential: O(2*4f) = '''O(8f)''' *galloping: = O(2f * (log 4 + 1)) = '''O(6f)''' '''L = 8f''' *binary: O(2f * log 8f) = O(2f log 8 + 2f log f) = '''O(6f + 2f log f)''' *sequential: '''O(16f)''' *galloping: O(2f * (log 8 + 1)) = O(2f * 4) = '''O(8f)'''

-- Feb 17 In-Class Exercise Thread

Search Algorithms: a. Binary search O(n*l*log(l*L)) b. Sequential Search O(n*l*L) c. Galloping Search O(n*l*(1 + log(l*L/l))) Then, apply n = 2 and L = (1,2,4,8). 1. n=2,L=1 a. Binary Search = O(2*l*log(l*1)) = O(2l*log(l)) b. Sequential Search = O(2*l*1) = O(2l) c. Galloping Search = O(2*l*(1 + log(l*1/l))) = O(2l*(1 + log(1))) = O(2l*(1 + 0)) = O(2l) 2. n=2,L=2 a. Binary Search = O(2*l*log(l*2)) = O(2l*(log(l) + log(2))) = O(2l*(log(l) + 1)) = O(2l*log(l) + 2l) b. Sequential Search = O(2*l*2) = O(4l) c. Galloping Search = O(2*l*(1 + log(l*2/l))) = O(2l*(1 + log(2))) = O(2l*(1 + 1)) = O(4l) 3. n=2,L=4 a. Binary Search = O(2*l*log(l*4)) = O(2l*(log(l) + log(4))) = O(2l*(log(l) + 2)) = O(2l*log(l) + 4l) b. Sequential Search = O(2*l*4) = O(8l) c. Galloping Search = O(2*l*(1 + log(l*4/l))) = O(2*l*(1 + log(4))) = O(2l*(1 + 2)) = O(6l) 4. n=2,L=8 a. Binary Search = O(2*l*log(l*8)) = O(2*l*(log(l) + log(8))) = O(2*l*log(l) + 2*l*3)) = O(2l*log(l) + 6l) b. Sequential Search = O(2*l*8) = O(16l) c. Galloping Search = O(2*l*(1 + log(l*8/l))) = O(2*l*(1 + 3)) = O(8l)

<nowiki> Search Algorithms: a. Binary search O(n*l*log(l*L)) b. Sequential Search O(n*l*L) c. Galloping Search O(n*l*(1 + log(l*L/l))) Then, apply n = 2 and L = (1,2,4,8). 1. n=2,L=1 a. Binary Search = O(2*l*log(l*1)) = O(2l*log(l)) b. Sequential Search = O(2*l*1) = O(2l) c. Galloping Search = O(2*l*(1 + log(l*1/l))) = O(2l*(1 + log(1))) = O(2l*(1 + 0)) = O(2l) 2. n=2,L=2 a. Binary Search = O(2*l*log(l*2)) = O(2l*(log(l) + log(2))) = O(2l*(log(l) + 1)) = O(2l*log(l) + 2l) b. Sequential Search = O(2*l*2) = O(4l) c. Galloping Search = O(2*l*(1 + log(l*2/l))) = O(2l*(1 + log(2))) = O(2l*(1 + 1)) = O(4l) 3. n=2,L=4 a. Binary Search = O(2*l*log(l*4)) = O(2l*(log(l) + log(4))) = O(2l*(log(l) + 2)) = O(2l*log(l) + 4l) b. Sequential Search = O(2*l*4) = O(8l) c. Galloping Search = O(2*l*(1 + log(l*4/l))) = O(2*l*(1 + log(4))) = O(2l*(1 + 2)) = O(6l) 4. n=2,L=8 a. Binary Search = O(2*l*log(l*8)) = O(2*l*(log(l) + log(8))) = O(2*l*log(l) + 2*l*3)) = O(2l*log(l) + 6l) b. Sequential Search = O(2*l*8) = O(16l) c. Galloping Search = O(2*l*(1 + log(l*8/l))) = O(2*l*(1 + 3)) = O(8l) </nowiki>

-- Feb 17 In-Class Exercise Thread

 Binary: O(n * l * log(L)
 Sequential: O(n * L)
 Galloping: O(n * l (log(L/l) + 1))

 Term 1 = f
 Term 2 = f, 2f, 4f, 8f

 n = 2

 ----- Case 1 -----
 Term 2 = f

 Binary: 
 O(2 * f * log(f)) 
 = O(2flog(f))

 Sequential: 
 O(2f)
 
 Galloping: 
 O(2 * f (log(f/f) + 1) 
 = O(2f+1) 
 = O(2f)
 
 - If terms are close, then Galloping is same as Sequential and at least as good as Binary.
 
 
 ----- Case 2 -----
 Term 2 = 2f
 
 Binary: 
 O(2 * f * log(2f)) 
 = O(2flog(2f)) 
 = O(2f(log(f)+ log2)) 
 = O(2f(log(f) + 1))
 = O(2flog(f) + 2f)
 
 Sequential: 
 O(2 * 2f) 
 = O(4f)
 
 Galloping: 
 O(2 * f (log(2f/f) + 1)) 
 = O(2f(log2 + 1)) 
 = O(2f + 2f)
 = O(4f)

 - If terms are still close, then Galloping is same as Sequential and at least as good as Binary.

 ----- Case 3 -----
 Term 2 = 4f

 Binary: 
 O(2 * f * log(4f)) 
 = O(2flog(4f)) 
 = O(2f(log4 + log(f))) 
 = O(4f + 2flog(f))

 Sequential: 
 O(2 * 4f) 
 = O(8f)
 
 Galloping: 
 O(2 * f (log(4f/f) + 1)) 
 = O(2f(log4 + 1)) 
 = O(4f + 2f) 
 = O(6f)

 - As terms get further apart, Galloping is better than Sequential and materially similar to Binary.

 ----- Case 4 -----
 Term 2 = 8f

 Binary: 
 O(2 * f * log(8f)) 
 = O(2flog(8f)) 
 = O(2f(log8 + log(f))) 
 = O(6f + 2flog(f))

 Sequential: 
 O(2 * 8f) 
 = O(16f)

 Galloping: 
 O(2 * f (log(8f/f) + 1)) 
 = O(2f(log(8)+1)) 
 = O(2f(3 + 1)) 
 = O(8f)

 - As terms get further apart, Galloping is better than Sequential and materially similar to Binary.

Binary: O(n * l * log(L) Sequential: O(n * L) Galloping: O(n * l (log(L/l) + 1)) Term 1 = f Term 2 = f, 2f, 4f, 8f n = 2 ----- Case 1 ----- Term 2 = f Binary: O(2 * f * log(f)) = O(2flog(f)) Sequential: O(2f) Galloping: O(2 * f (log(f/f) + 1) = O(2f+1) = O(2f) - If terms are close, then Galloping is same as Sequential and at least as good as Binary. ----- Case 2 ----- Term 2 = 2f Binary: O(2 * f * log(2f)) = O(2flog(2f)) = O(2f(log(f)+ log2)) = O(2f(log(f) + 1)) = O(2flog(f) + 2f) Sequential: O(2 * 2f) = O(4f) Galloping: O(2 * f (log(2f/f) + 1)) = O(2f(log2 + 1)) = O(2f + 2f) = O(4f) - If terms are still close, then Galloping is same as Sequential and at least as good as Binary. ----- Case 3 ----- Term 2 = 4f Binary: O(2 * f * log(4f)) = O(2flog(4f)) = O(2f(log4 + log(f))) = O(4f + 2flog(f)) Sequential: O(2 * 4f) = O(8f) Galloping: O(2 * f (log(4f/f) + 1)) = O(2f(log4 + 1)) = O(4f + 2f) = O(6f) - As terms get further apart, Galloping is better than Sequential and materially similar to Binary. ----- Case 4 ----- Term 2 = 8f Binary: O(2 * f * log(8f)) = O(2flog(8f)) = O(2f(log8 + log(f))) = O(6f + 2flog(f)) Sequential: O(2 * 8f) = O(16f) Galloping: O(2 * f (log(8f/f) + 1)) = O(2f(log(8)+1)) = O(2f(3 + 1)) = O(8f) - As terms get further apart, Galloping is better than Sequential and materially similar to Binary.