## 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

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

maggiemagnet
Posts: 358
Joined: Mon Dec 08, 2008 12:32 am
Contact:

### Re: finding largest n using an algorithm

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.
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.

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

### Re: finding largest n using an algorithm

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

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

maggiemagnet
Posts: 358
Joined: Mon Dec 08, 2008 12:32 am
Contact:

### Re: finding largest n using an algorithm

so for the first question n would be n<= 10 * 10^2/3?
How did you get this?
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)?