Proof by induction long question [closed]
up vote
-2
down vote
favorite
I've been trying to figure this question out for a while:
An algorithm takes one operation to sort an array with one item in it. When the number of items in the array increases from n to n+1, at most an additional 2n+1 operations are required. Use proof by induction to show that the number of operations required to sort the array with n>0 items in it requires at most n2 operations.
I understand proof by induction, and have done several examples pf shorter-style questions however can't think how to extract the required information from this question.
Thanks in advance.
induction
asked Nov 14 at 12:24
Mike
31
closed as off-topic by amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos Nov 15 at 10:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
-2
down vote
favorite
I've been trying to figure this question out for a while:
An algorithm takes one operation to sort an array with one item in it. When the number of items in the array increases from n to n+1, at most an additional 2n+1 operations are required. Use proof by induction to show that the number of operations required to sort the array with n>0 items in it requires at most n2 operations.
I understand proof by induction, and have done several examples pf shorter-style questions however can't think how to extract the required information from this question.
Thanks in advance.
induction
asked Nov 14 at 12:24
Mike
31
closed as off-topic by amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos Nov 15 at 10:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28
add a comment |
up vote
-2
down vote
favorite
up vote
-2
down vote
favorite
I've been trying to figure this question out for a while:
An algorithm takes one operation to sort an array with one item in it. When the number of items in the array increases from n to n+1, at most an additional 2n+1 operations are required. Use proof by induction to show that the number of operations required to sort the array with n>0 items in it requires at most n2 operations.
I understand proof by induction, and have done several examples pf shorter-style questions however can't think how to extract the required information from this question.
Thanks in advance.
induction
asked Nov 14 at 12:24
Mike
31
I've been trying to figure this question out for a while:
An algorithm takes one operation to sort an array with one item in it. When the number of items in the array increases from n to n+1, at most an additional 2n+1 operations are required. Use proof by induction to show that the number of operations required to sort the array with n>0 items in it requires at most n2 operations.
I understand proof by induction, and have done several examples pf shorter-style questions however can't think how to extract the required information from this question.
Thanks in advance.
induction
induction
asked Nov 14 at 12:24
Mike
31
asked Nov 14 at 12:24
Mike
31
asked Nov 14 at 12:24
Mike
31
asked Nov 14 at 12:24
Mike
31
asked Nov 14 at 12:24
Mike
31
31
closed as off-topic by amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos Nov 15 at 10:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos Nov 15 at 10:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Cesareo, max_zorn, Delta-u, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28
add a comment |
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Basis for induction: For n = 1, the result holds.
Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.
Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step
=$k^2+(2k+1)$
=$(k+1)^2$
Hence proved
Hope it is helpful
answered Nov 14 at 12:31
Crazy for maths
57210
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Basis for induction: For n = 1, the result holds.
Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.
Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step
=$k^2+(2k+1)$
=$(k+1)^2$
Hence proved
Hope it is helpful
answered Nov 14 at 12:31
Crazy for maths
57210
add a comment |
up vote
0
down vote
accepted
Basis for induction: For n = 1, the result holds.
Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.
Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step
=$k^2+(2k+1)$
=$(k+1)^2$
Hence proved
Hope it is helpful
answered Nov 14 at 12:31
Crazy for maths
57210
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Basis for induction: For n = 1, the result holds.
Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.
Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step
=$k^2+(2k+1)$
=$(k+1)^2$
Hence proved
Hope it is helpful
answered Nov 14 at 12:31
Crazy for maths
57210
Basis for induction: For n = 1, the result holds.
Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.
Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step
=$k^2+(2k+1)$
=$(k+1)^2$
Hence proved
Hope it is helpful
answered Nov 14 at 12:31
Crazy for maths
57210
answered Nov 14 at 12:31
Crazy for maths
57210
answered Nov 14 at 12:31
Crazy for maths
57210
answered Nov 14 at 12:31
Crazy for maths
57210
57210
add a comment |
add a comment |
Inductively suppose we are done out to stage $k$. So stage $k$ requires at most $k^2$ operations. Now, how many operations might stage $k+1$ require? How does that compare to $(k+1)^2$?
– lulu
Nov 14 at 12:26
General note: when confused, it's always a good idea to keep things explicit. As usual, we are handed the case $n=1$ as an assumption, So, then, what about $n=2$? $n=3$? Keep going until you see a general pattern.
– lulu
Nov 14 at 12:28