Couple Theory Questions - Topic

Member

Posts: 20,319

Joined: Jun 23 2007

Gold: 3.01

Oct 10 2013 06:38pm

This post is a violation of the site rules and appropriate action was taken.

Have a couple questions, real easy. Just simple theory stuff really.

Willing to pay $10 of steam games or buy fg or w.e is legal here for assistane.

(working in c++ here btw)

1) Need to find the equation to determine when it is most beneficial to use binary search or sequential search. Say on an unsorted list with 1024 items.
Sequential taking average 512 searches here while binary taking up to 10. Although that requires the list being sorted. So need to find number of searches to do one insertion sort + binary search compared to a sequential search and at what point is it more beneficial to do one over the other.

2) Need to find a formal algorithm to find prime numbers Mainly looking at like prime numbers under 100 here, using the info That if say 7 is a prime number, you know that all its multiples aren't (14,21,28, etc).

This post was edited by gramkracka22 on Oct 10 2013 06:50pm

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Oct 10 2013 06:53pm

#1: find the threshold where O(sort) + O(binary search) = O(linear search)
ceiling(nlogn) + ceiling(logn) = ceiling(n/2)

graph it and see where they intersect. n's gotta be pretty low.

if you insist on insertion sort, then use n^2 instead of nlogn.

or are you trying to do "experiments"? eg write both algorithms and run it a dozen times for n = 1 to n = 100? if so, what do you need help with?

#2: lots of algorithms. what is the problem you're having? imo look at Sieve of Eratosthenes.

This post was edited by carteblanche on Oct 10 2013 06:58pm

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Oct 10 2013 07:46pm

Stick to the topic, not pms.

Quote

This is pretty much the question at hand

Quote
If the list has 1024 items (lg1024 = 10) at what point (the number of
searches) does sorting the list first and using binary search pay off? How does your answer
change if the list has 2048 items? Is there a general statement that you can make about this
problem?

With the equation n^2 +logn = n/2, n is equal to 0.8. Seems like I am off here

Tyvm

oh, i misread it. i thought it was for the first search only.

so the time it takes to do x searches for a list of n items is a bit different:

O(sort) + O(binary search)*x = O(sequential search) * x

try that. n is fixed here, whereas it was a variable last time.

This post was edited by carteblanche on Oct 10 2013 07:48pm

gramkracka22

Member

Posts: 20,319

Joined: Jun 23 2007

Gold: 3.01

Oct 10 2013 08:37pm

Quote (carteblanche @ Oct 10 2013 07:46pm)

Stick to the topic, not pms.

oh, i misread it. i thought it was for the first search only.

so the time it takes to do x searches for a list of n items is a bit different:

O(sort) + O(binary search)*x = O(sequential search) * x

try that. n is fixed here, whereas it was a variable last time.

confussed by new equation, so there are two variables there now x, and n? Say n is fixed, so it would be 1024 if that is how many items there are to search.

log1024*x+ 1024^2=1024/2*x

If that is the case, believe it is like x ~= 2075

This post was edited by gramkracka22 on Oct 10 2013 08:41pm

Azrad

Member

Posts: 10,812

Joined: Oct 15 2009

Gold: Locked

Warn: 20%

Oct 10 2013 10:06pm

Quote (gramkracka22 @ Oct 10 2013 05:38pm)

2) Need to find a formal algorithm to find prime numbers Mainly looking at like prime numbers under 100 here, using the info That if say 7 is a prime number, you know that all its multiples aren't (14,21,28, etc).

Not the best, but this is one I wrote recently (in python). Prints list of primes from 2 to 100

Code

import math

def IsPrime(input_number):
if input_number == 2:
return True
if not input_number%2:
return False
max = int(math.ceil((math.sqrt(input_number)))+1)
for i in range (3,max,2):
if not input_number%i:
return False
return True

for i in range(2,101):
if IsPrime(i):
print i

This post was edited by Azrad on Oct 10 2013 10:08pm

Go Back To Programming & Development Topic List