1/Which grows faster, 2^n or n! ? Why?
please answer mathmetically
2/. What is the Big-O running time for this code? Explain your answer.
if ( i < 20 )
for (int i=0; i<numItems; i++)
{
System.out.println(i);
}
else
println("too many");
please answer mathmetically
3/ What is the Big-O running time for this code? Explain your answer.
i = numItems;
while (i > 0)
i = i / 2;
please answer mathmetically
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
how many times does System.out.println(i); execute as numItems gets large?
how many times does i = i / 2 execute as numItems gets large?
If you double numItems, how does the number of times System.out.println(i); executes change?
If you double numItems, how does the number of times i = i / 2; executes change?
"n! > 2^n for n>4" is not enough to answer the question (e.g. 10*2^n > 2^n does not imply that 10*2^n grows faster than 2^n)
However, one finds lim_{n -> oo} (2^n)/n! = 0 because -- with a_n := (2^n)/n! -- we have a_{n+1} < 1/2 a_n for n>3.
BTW, what were your own efforts so far for this homework assignment?
Are you sure the code given for Q2 is correct? Note that there are two different variables named i (which looks like bad coding and worse didactics)
Q3: Is anything said about the type of variable i? Integer? IEEE float? Idealised arbitray precision real number?
(1)
If 2^n = o(n!) then for any k > 0 there exists N st for n>N then
2^n < kn!
Since n! > 2^n for n>4 we can write choose k=1 and N=4.
NB: We use induction to show n! > 2^n for n>4.
Clearly n! > 2^n is true for n=5
Assume true for n and less then using the inductive assumption
(n+1)! = (n+1)*n! > (n+1) 2^n > 2*2^n > 2^(n+1) if n>4
Hence since true for n=5 by the principle of induction true for all n.
(2) The code is executed no more than 20 times regardless of numItems it there for is bounded by a constant that is independent of numItems. it is O(1)
(3) You continously divide by 2 until you you reach 1, ie you execute the loop n times where n is the smallest integer st
2^n => numItems
n = ceiling( lg(numItems) )
n =O ( lg(numItems) )
(2) is of course O(numItems) and not O(1), but that is because the code is written very strangely: If (the original) i is less than 20, then a new int variable i is "created" having the for loop as scope and that loop repeats numItems times.
BTW, asking what is "the" Big-O is a bit misleading.
Of course Q2 is not only in O(numItems), but also in O(numItems^2+7).
Even if you should determine a "best possible" function this is unclear -- O(numItems) is "as best as" O(numItems + sin(numItems) since these O()'s are in fact the same sets of functions; then again O( ( |i-19|-|i-20|+1)*numItems + 1) might be considered best as the running time depends on two input parameters numItems and i.
sidd_barai,
Although the comments already explain properly your doubts, we can add a little bit more words.
2) Which grows faster, 2^n or n! ?
Already clearly explained
2) Big-O running time for this code
if ( i < 20 )
for (int i=0; i<numItems; i++)
{
System.out.println(i);
}
else
println("too many");
Despite bad practice in the code, it is correct on the syntax and scope definition: the scope of the int variable i declared in the for loop is limited to such loop, say, it is visible only by the loop control (comparing i to numItems and incrementing it) and the print statement.
As stated by GwynforWeb, the bound function (if ...) is O(1). The loop, executed conditionally, is clearly linear to numItems, say O(numItems), in this case treated as a constant, so the loop is O(1) as well.
3) running time for
i = numItems;
while (i > 0)
i = i / 2;
Strictly from math point-of-view, the running time is the eternity.
Anyway, a such program will stop at a moment due hardware limitation (there is no infinite number of bits in the computer) and software (if this is C language and i is an int type, then the program will stop when i=1, then i=0; if the type is double, then the program will run more times, but the big O notation for the complexity will remain the same: O (log n).
Jose
Business Accounts
Answer for Membership
by: ozoPosted on 2009-09-12 at 01:10:46ID: 25315588
n! > 2^n for n>4