I made a function to find a word in a list of words by splitting it in half each time — how does each if...
0
My program is here. It is assumed that lst is a list of words in alphabetical order.
My question is if the time complexity is changed by each if statement.
When compared to just using x in s (which has a time complexity of O(n)), it is faster, right? From what I know the time complexity of this program is O(N/8), unless each if statement counts, in which it should be N/4?.
Thanks for the help.
def is_in(val, lst):
"""
is_in is designed to check if a word is in a list of words in alphabetical order.
:param val: the word to look for
:param lst: the lst of words to check
"""
curlen = len(lst) # saving processing power
if ((curlen == 1) and (lst[0] != val)) or (curlen == 0): # base case
return False
else:
center = curlen // 2
pivot = lst[center]
# print("pivot: " + str(pivot))
# print("val: " + str(val))
if pivot == val: # base case 2
return True
elif pivot > val:
return is_in(val, lst[:center])
else:
return is_in(val, lst[center:])
python-3.x time-complexity
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
|
show 4 more comments
0
My program is here. It is assumed that lst is a list of words in alphabetical order.
My question is if the time complexity is changed by each if statement.
When compared to just using x in s (which has a time complexity of O(n)), it is faster, right? From what I know the time complexity of this program is O(N/8), unless each if statement counts, in which it should be N/4?.
Thanks for the help.
def is_in(val, lst):
"""
is_in is designed to check if a word is in a list of words in alphabetical order.
:param val: the word to look for
:param lst: the lst of words to check
"""
curlen = len(lst) # saving processing power
if ((curlen == 1) and (lst[0] != val)) or (curlen == 0): # base case
return False
else:
center = curlen // 2
pivot = lst[center]
# print("pivot: " + str(pivot))
# print("val: " + str(val))
if pivot == val: # base case 2
return True
elif pivot > val:
return is_in(val, lst[:center])
else:
return is_in(val, lst[center:])
python-3.x time-complexity
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It also seems you're trying to write your own version ofbisectwhich is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.
– Jon Clements♦
Nov 24 '18 at 21:18
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C levelintest...
– Jon Clements♦
Nov 24 '18 at 21:33
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36
|
show 4 more comments
0
0
0
My program is here. It is assumed that lst is a list of words in alphabetical order.
My question is if the time complexity is changed by each if statement.
When compared to just using x in s (which has a time complexity of O(n)), it is faster, right? From what I know the time complexity of this program is O(N/8), unless each if statement counts, in which it should be N/4?.
Thanks for the help.
def is_in(val, lst):
"""
is_in is designed to check if a word is in a list of words in alphabetical order.
:param val: the word to look for
:param lst: the lst of words to check
"""
curlen = len(lst) # saving processing power
if ((curlen == 1) and (lst[0] != val)) or (curlen == 0): # base case
return False
else:
center = curlen // 2
pivot = lst[center]
# print("pivot: " + str(pivot))
# print("val: " + str(val))
if pivot == val: # base case 2
return True
elif pivot > val:
return is_in(val, lst[:center])
else:
return is_in(val, lst[center:])
python-3.x time-complexity
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
My program is here. It is assumed that lst is a list of words in alphabetical order.
My question is if the time complexity is changed by each if statement.
When compared to just using x in s (which has a time complexity of O(n)), it is faster, right? From what I know the time complexity of this program is O(N/8), unless each if statement counts, in which it should be N/4?.
Thanks for the help.
def is_in(val, lst):
"""
is_in is designed to check if a word is in a list of words in alphabetical order.
:param val: the word to look for
:param lst: the lst of words to check
"""
curlen = len(lst) # saving processing power
if ((curlen == 1) and (lst[0] != val)) or (curlen == 0): # base case
return False
else:
center = curlen // 2
pivot = lst[center]
# print("pivot: " + str(pivot))
# print("val: " + str(val))
if pivot == val: # base case 2
return True
elif pivot > val:
return is_in(val, lst[:center])
else:
return is_in(val, lst[center:])
python-3.x time-complexity
python-3.x time-complexity
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
edited Nov 24 '18 at 21:20
meowgoesthedog
10k41528
10k41528
asked Nov 24 '18 at 21:14
Adin DAdin D
1
asked Nov 24 '18 at 21:14
Adin DAdin D
1
asked Nov 24 '18 at 21:14
Adin DAdin D
1
1
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It also seems you're trying to write your own version ofbisectwhich is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.
– Jon Clements♦
Nov 24 '18 at 21:18
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C levelintest...
– Jon Clements♦
Nov 24 '18 at 21:33
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36
|
show 4 more comments
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It also seems you're trying to write your own version ofbisectwhich is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.
– Jon Clements♦
Nov 24 '18 at 21:18
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C levelintest...
– Jon Clements♦
Nov 24 '18 at 21:33
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It also seems you're trying to write your own version of
bisect which is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.– Jon Clements♦
Nov 24 '18 at 21:18
It also seems you're trying to write your own version of
bisect which is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.– Jon Clements♦
Nov 24 '18 at 21:18
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C level
in test...– Jon Clements♦
Nov 24 '18 at 21:33
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C level
in test...– Jon Clements♦
Nov 24 '18 at 21:33
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36
|
show 4 more comments
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f53462430%2fi-made-a-function-to-find-a-word-in-a-list-of-words-by-splitting-it-in-half-each%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f53462430%2fi-made-a-function-to-find-a-word-in-a-list-of-words-by-splitting-it-in-half-each%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
It won't be faster than linearly scanning the original list... you'll find you're actually making it more complicated by slicing the list into chunks (creating new lists each time) while you keep halving it... at which point you could have O(N)'d the original list a few times probably. Recursion certainly doesn't help here...
– Jon Clements♦
Nov 24 '18 at 21:17
It also seems you're trying to write your own version of
bisectwhich is a builtin module in Python... you'll find you can do what you're trying to do without recursion and just indexing rather than slicing whole parts.– Jon Clements♦
Nov 24 '18 at 21:18
@JonClements Some other people told me that mine is O(logN) and that x in s is O(N). How would mine be slower if it is only checking a single value each time rather than going through and entire list?
– Adin D
Nov 24 '18 at 21:31
You're using recursion and creating copies of portions of the list for a start... so you're creating more variables, building up a stack etc... that's a lot more involved than a simple C level
intest...– Jon Clements♦
Nov 24 '18 at 21:33
@JonClements So doing bisect.bisect(legal_list, word) returns the position of the word, assuming it is in the file? It appears to return a position even if the word isn't in the list.
– Adin D
Nov 24 '18 at 21:36