finding largest n using an algorithm

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
ricky.rick
Posts: 3
Joined: Sun Feb 23, 2014 8:55 am
Contact:

finding largest n using an algorithm

Postby ricky.rick » 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?

User avatar
maggiemagnet
Posts: 315
Joined: Mon Dec 08, 2008 12:32 am
Contact:

Re: finding largest n using an algorithm

Postby maggiemagnet » 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:

ricky.rick
Posts: 3
Joined: Sun Feb 23, 2014 8:55 am
Contact:

Re: finding largest n using an algorithm

Postby ricky.rick » 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
Contact:

Re: finding largest n using an algorithm

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

b) (5log(10))/log(3)
c) (3X(10/3*10^2/3*log(3))/log(3)??

User avatar
maggiemagnet
Posts: 315
Joined: Mon Dec 08, 2008 12:32 am
Contact:

Re: finding largest n using an algorithm

Postby maggiemagnet » 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:


Return to “Discrete Math”