finding largest n using an algorithm

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

finding largest n using an algorithm

Postby ricky.rick on Sun Feb 23, 2014 8:58 am

So I am confused on this problem for my discrete math class, I didn't know if there was a specific formula you were supposed to use or what. The question is "What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^-6 seconds, with these functions?
a. f(n)= n^3
b. f(n)= 3^n
c. f(n)= 3^n * n^3
Can someone please help me with these answers and explain how they got them?
ricky.rick
 
Posts: 3
Joined: Sun Feb 23, 2014 8:55 am

Sponsor

Sponsor
 

Re: finding largest n using an algorithm

Postby maggiemagnet on Sun Feb 23, 2014 8:09 pm

ricky.rick wrote:So I am confused on this problem for my discrete math class, I didn't know if there was a specific formula you were supposed to use or what. The question is "What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^-6 seconds, with these functions?

I think you're just supposed to use the information they've given you. You don't have to come up with anything fancy. Since each operation takes 10^(-6) = 0.000001 = 1/100,000 seconds, then you can't do more than 100,000 operations, no matter what. That's your cap.

ricky.rick wrote:a. f(n)= n^3

This says that you need n^3 operations for this particular problem ("f"). Since you can't do more than 100,000 operations, then n^3 <= 100,000. So what is n? Do the same thing for the other parts, too.
:clap:
User avatar
maggiemagnet
 
Posts: 302
Joined: Mon Dec 08, 2008 12:32 am

Re: finding largest n using an algorithm

Postby ricky.rick on Tue Feb 25, 2014 3:14 am

so for the first question n would be n<= 10 * 10^2/3?
ricky.rick
 
Posts: 3
Joined: Sun Feb 23, 2014 8:55 am

Re: finding largest n using an algorithm

Postby ricky.rick on Tue Feb 25, 2014 3:19 am

b) (5log(10))/log(3)
c) (3X(10/3*10^2/3*log(3))/log(3)??
ricky.rick
 
Posts: 3
Joined: Sun Feb 23, 2014 8:55 am

Re: finding largest n using an algorithm

Postby maggiemagnet on Tue Feb 25, 2014 1:34 pm

ricky.rick wrote:so for the first question n would be n<= 10 * 10^2/3?

How did you get this?

ricky.rick wrote:b) (5log(10))/log(3)
c) (3X(10/3*10^2/3*log(3))/log(3)??

How did you get these? Why is there a variable in your number for (c)?
:clap:
User avatar
maggiemagnet
 
Posts: 302
Joined: Mon Dec 08, 2008 12:32 am


Return to Discrete Math

cron