Complexity analysis for while loop + list.insert()
up vote
-1
down vote
favorite
I have the following code for merging two sorted arrays in-place:
def mergeArrays(a1,a2,m,n):
i, j, k = m-1, n-1, m+n-1
while i >=0 and j >=0:
if a1[i] >= a2[j]:
i-=1
else:
a1.insert(i+1,a2[j])
j-=1
return a1
where
a = [1, 5, 9, 10, 15, 20]
b = [2, 3, 8, 13]
m,n = len(a), len(b)
I want to understand what will be the time complexity of the above code. From my limited understanding, the outer while loop will run O(n) times, and list.insert() takes O(n) time to insert an item. So does that make the full program run in O(n*n)?
python complexity
asked yesterday
ajaanbaahu
1914
add a comment |
up vote
-1
down vote
favorite
I have the following code for merging two sorted arrays in-place:
def mergeArrays(a1,a2,m,n):
i, j, k = m-1, n-1, m+n-1
while i >=0 and j >=0:
if a1[i] >= a2[j]:
i-=1
else:
a1.insert(i+1,a2[j])
j-=1
return a1
where
a = [1, 5, 9, 10, 15, 20]
b = [2, 3, 8, 13]
m,n = len(a), len(b)
I want to understand what will be the time complexity of the above code. From my limited understanding, the outer while loop will run O(n) times, and list.insert() takes O(n) time to insert an item. So does that make the full program run in O(n*n)?
python complexity
asked yesterday
ajaanbaahu
1914
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
I have the following code for merging two sorted arrays in-place:
def mergeArrays(a1,a2,m,n):
i, j, k = m-1, n-1, m+n-1
while i >=0 and j >=0:
if a1[i] >= a2[j]:
i-=1
else:
a1.insert(i+1,a2[j])
j-=1
return a1
where
a = [1, 5, 9, 10, 15, 20]
b = [2, 3, 8, 13]
m,n = len(a), len(b)
I want to understand what will be the time complexity of the above code. From my limited understanding, the outer while loop will run O(n) times, and list.insert() takes O(n) time to insert an item. So does that make the full program run in O(n*n)?
python complexity
asked yesterday
ajaanbaahu
1914
I have the following code for merging two sorted arrays in-place:
def mergeArrays(a1,a2,m,n):
i, j, k = m-1, n-1, m+n-1
while i >=0 and j >=0:
if a1[i] >= a2[j]:
i-=1
else:
a1.insert(i+1,a2[j])
j-=1
return a1
where
a = [1, 5, 9, 10, 15, 20]
b = [2, 3, 8, 13]
m,n = len(a), len(b)
I want to understand what will be the time complexity of the above code. From my limited understanding, the outer while loop will run O(n) times, and list.insert() takes O(n) time to insert an item. So does that make the full program run in O(n*n)?
python complexity
python complexity
asked yesterday
ajaanbaahu
1914
asked yesterday
ajaanbaahu
1914
asked yesterday
ajaanbaahu
1914
asked yesterday
ajaanbaahu
1914
asked yesterday
ajaanbaahu
1914
1914
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207505%2fcomplexity-analysis-for-while-loop-list-insert%23new-answer', 'question_page');
}
);
Post as a guest
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
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
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
