How can I justify and analyze code's running time, is it O(n)?
How can I justify and analyze the running time of the code with recursive call, is it O(n)?
A = [10,8,7,6,5]
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
python recursion time runtime time-complexity
edited Nov 19 at 22:09
halfer
14.3k758108
asked Nov 17 at 21:03
collisior
62
add a comment |
How can I justify and analyze the running time of the code with recursive call, is it O(n)?
A = [10,8,7,6,5]
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
python recursion time runtime time-complexity
edited Nov 19 at 22:09
halfer
14.3k758108
asked Nov 17 at 21:03
collisior
62
2
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater thenO(n)because those calls tomax()andindex()each takeO(n)time. So if this recursive call is donentimes it would beO(n^2)
– Karl
Nov 17 at 21:14
add a comment |
How can I justify and analyze the running time of the code with recursive call, is it O(n)?
A = [10,8,7,6,5]
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
python recursion time runtime time-complexity
edited Nov 19 at 22:09
halfer
14.3k758108
asked Nov 17 at 21:03
collisior
62
How can I justify and analyze the running time of the code with recursive call, is it O(n)?
A = [10,8,7,6,5]
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
python recursion time runtime time-complexity
python recursion time runtime time-complexity
edited Nov 19 at 22:09
halfer
14.3k758108
asked Nov 17 at 21:03
collisior
62
edited Nov 19 at 22:09
halfer
14.3k758108
asked Nov 17 at 21:03
collisior
62
edited Nov 19 at 22:09
halfer
14.3k758108
edited Nov 19 at 22:09
halfer
14.3k758108
edited Nov 19 at 22:09
halfer
14.3k758108
14.3k758108
asked Nov 17 at 21:03
collisior
62
asked Nov 17 at 21:03
collisior
62
asked Nov 17 at 21:03
collisior
62
62
2
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater thenO(n)because those calls tomax()andindex()each takeO(n)time. So if this recursive call is donentimes it would beO(n^2)
– Karl
Nov 17 at 21:14
add a comment |
2
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater thenO(n)because those calls tomax()andindex()each takeO(n)time. So if this recursive call is donentimes it would beO(n^2)
– Karl
Nov 17 at 21:14
2
2
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater then
O(n) because those calls to max() and index() each take O(n) time. So if this recursive call is done n times it would be O(n^2)– Karl
Nov 17 at 21:14
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater then
O(n) because those calls to max() and index() each take O(n) time. So if this recursive call is done n times it would be O(n^2)– Karl
Nov 17 at 21:14
add a comment |
2 Answers
2
active
oldest
votes
Here's the breakdown of it:
def Algorithm(A):
ai = max(A) # O(n)
i = A.index(ai) # O(n)
A[i] = 0 # O(1)
aj = max(A) # O(n)
A[i] = abs(ai - aj) # O(1)
j = A.index(aj) # O(n)
A[j] = 0 # O(1)
if aj == 0: # O(1)
return ai # O(1)
return Algorithm(A) # recursive call, called up to n times recursively
The last recursive call is called as long as max(A) is not 0, which is n times, in the worst case, if all are positive.
So, everything up to the last line is O(n), and the last line makes everything run n times, so the total of it is O(n^2)
answered Nov 17 at 22:04
zvone
9,2252044
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating# recursive call, called up to n times recursively.
– quant
Nov 17 at 22:11
add a comment |
At first, I was a bit sceptic whether your algorithm really runs in O(n). Also the following program
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = ,
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
measures the running time of the algorithm for different randomly generated lists (and plots this afterwards). The result
clearly supports a non-linear grow. So said otherwise since the algorithm is in O(n^2) complexity it is not provable that it runs within O(n).
answered Nov 17 at 22:10
quant
1,58411526
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53355560%2fhow-can-i-justify-and-analyze-codes-running-time-is-it-on%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Here's the breakdown of it:
def Algorithm(A):
ai = max(A) # O(n)
i = A.index(ai) # O(n)
A[i] = 0 # O(1)
aj = max(A) # O(n)
A[i] = abs(ai - aj) # O(1)
j = A.index(aj) # O(n)
A[j] = 0 # O(1)
if aj == 0: # O(1)
return ai # O(1)
return Algorithm(A) # recursive call, called up to n times recursively
The last recursive call is called as long as max(A) is not 0, which is n times, in the worst case, if all are positive.
So, everything up to the last line is O(n), and the last line makes everything run n times, so the total of it is O(n^2)
answered Nov 17 at 22:04
zvone
9,2252044
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating# recursive call, called up to n times recursively.
– quant
Nov 17 at 22:11
add a comment |
Here's the breakdown of it:
def Algorithm(A):
ai = max(A) # O(n)
i = A.index(ai) # O(n)
A[i] = 0 # O(1)
aj = max(A) # O(n)
A[i] = abs(ai - aj) # O(1)
j = A.index(aj) # O(n)
A[j] = 0 # O(1)
if aj == 0: # O(1)
return ai # O(1)
return Algorithm(A) # recursive call, called up to n times recursively
The last recursive call is called as long as max(A) is not 0, which is n times, in the worst case, if all are positive.
So, everything up to the last line is O(n), and the last line makes everything run n times, so the total of it is O(n^2)
answered Nov 17 at 22:04
zvone
9,2252044
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating# recursive call, called up to n times recursively.
– quant
Nov 17 at 22:11
add a comment |
Here's the breakdown of it:
def Algorithm(A):
ai = max(A) # O(n)
i = A.index(ai) # O(n)
A[i] = 0 # O(1)
aj = max(A) # O(n)
A[i] = abs(ai - aj) # O(1)
j = A.index(aj) # O(n)
A[j] = 0 # O(1)
if aj == 0: # O(1)
return ai # O(1)
return Algorithm(A) # recursive call, called up to n times recursively
The last recursive call is called as long as max(A) is not 0, which is n times, in the worst case, if all are positive.
So, everything up to the last line is O(n), and the last line makes everything run n times, so the total of it is O(n^2)
answered Nov 17 at 22:04
zvone
9,2252044
Here's the breakdown of it:
def Algorithm(A):
ai = max(A) # O(n)
i = A.index(ai) # O(n)
A[i] = 0 # O(1)
aj = max(A) # O(n)
A[i] = abs(ai - aj) # O(1)
j = A.index(aj) # O(n)
A[j] = 0 # O(1)
if aj == 0: # O(1)
return ai # O(1)
return Algorithm(A) # recursive call, called up to n times recursively
The last recursive call is called as long as max(A) is not 0, which is n times, in the worst case, if all are positive.
So, everything up to the last line is O(n), and the last line makes everything run n times, so the total of it is O(n^2)
answered Nov 17 at 22:04
zvone
9,2252044
edited Nov 17 at 22:09
answered Nov 17 at 22:04
zvone
9,2252044
answered Nov 17 at 22:04
zvone
9,2252044
answered Nov 17 at 22:04
zvone
9,2252044
9,2252044
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating# recursive call, called up to n times recursively.
– quant
Nov 17 at 22:11
add a comment |
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating# recursive call, called up to n times recursively.
– quant
Nov 17 at 22:11
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
but isn't the question to prove that it is in O(n)? For this, we need to prove that how often the last recursive call is done does not depend on the size of the input.
– quant
Nov 17 at 22:05
+1 However from the analysis I posted, I think you are right with stating
# recursive call, called up to n times recursively.– quant
Nov 17 at 22:11
+1 However from the analysis I posted, I think you are right with stating
# recursive call, called up to n times recursively.– quant
Nov 17 at 22:11
add a comment |
At first, I was a bit sceptic whether your algorithm really runs in O(n). Also the following program
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = ,
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
measures the running time of the algorithm for different randomly generated lists (and plots this afterwards). The result
clearly supports a non-linear grow. So said otherwise since the algorithm is in O(n^2) complexity it is not provable that it runs within O(n).
answered Nov 17 at 22:10
quant
1,58411526
add a comment |
At first, I was a bit sceptic whether your algorithm really runs in O(n). Also the following program
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = ,
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
measures the running time of the algorithm for different randomly generated lists (and plots this afterwards). The result
clearly supports a non-linear grow. So said otherwise since the algorithm is in O(n^2) complexity it is not provable that it runs within O(n).
answered Nov 17 at 22:10
quant
1,58411526
add a comment |
At first, I was a bit sceptic whether your algorithm really runs in O(n). Also the following program
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = ,
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
measures the running time of the algorithm for different randomly generated lists (and plots this afterwards). The result
clearly supports a non-linear grow. So said otherwise since the algorithm is in O(n^2) complexity it is not provable that it runs within O(n).
answered Nov 17 at 22:10
quant
1,58411526
At first, I was a bit sceptic whether your algorithm really runs in O(n). Also the following program
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = ,
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
measures the running time of the algorithm for different randomly generated lists (and plots this afterwards). The result
clearly supports a non-linear grow. So said otherwise since the algorithm is in O(n^2) complexity it is not provable that it runs within O(n).
answered Nov 17 at 22:10
quant
1,58411526
answered Nov 17 at 22:10
quant
1,58411526
answered Nov 17 at 22:10
quant
1,58411526
answered Nov 17 at 22:10
quant
1,58411526
1,58411526
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53355560%2fhow-can-i-justify-and-analyze-codes-running-time-is-it-on%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Can you give a description of what the function is supposed to do? Is it sorting the list? And it seems like it is greater then
O(n)because those calls tomax()andindex()each takeO(n)time. So if this recursive call is donentimes it would beO(n^2)– Karl
Nov 17 at 21:14