Improving Time Complexity
1
I would appreciate some feedback with regards to Big-O (time-complexity) of loops, or, ways to improve it.
Let's take the following:
var pairs = 0;
HashSet<int> hs = new HashSet<int>(n);
for (var i = 0; i < ar.Length; i++)
if(!hs.Contains(ar[i]))
hs.Add(ar[i]);
else
pairs++;
hs.Remove(ar[i]);
return pairs;
From what I can determine, the worst-case time-complexity of the above is: O(n), because of the loop.
Are the any way of improving this, to bring the time-complexity as close to O(1) as possible?
PS: I'm pretty sure that the the above will never be O(1).
Thank you
c# time-complexity big-o
asked Nov 12 at 15:14
Jaco
61
|
show 9 more comments
1
I would appreciate some feedback with regards to Big-O (time-complexity) of loops, or, ways to improve it.
Let's take the following:
var pairs = 0;
HashSet<int> hs = new HashSet<int>(n);
for (var i = 0; i < ar.Length; i++)
if(!hs.Contains(ar[i]))
hs.Add(ar[i]);
else
pairs++;
hs.Remove(ar[i]);
return pairs;
From what I can determine, the worst-case time-complexity of the above is: O(n), because of the loop.
Are the any way of improving this, to bring the time-complexity as close to O(1) as possible?
PS: I'm pretty sure that the the above will never be O(1).
Thank you
c# time-complexity big-o
asked Nov 12 at 15:14
Jaco
61
2
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
what isar? alsoif(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.
– styx
Nov 12 at 15:18
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
1
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25
|
show 9 more comments
1
1
1
I would appreciate some feedback with regards to Big-O (time-complexity) of loops, or, ways to improve it.
Let's take the following:
var pairs = 0;
HashSet<int> hs = new HashSet<int>(n);
for (var i = 0; i < ar.Length; i++)
if(!hs.Contains(ar[i]))
hs.Add(ar[i]);
else
pairs++;
hs.Remove(ar[i]);
return pairs;
From what I can determine, the worst-case time-complexity of the above is: O(n), because of the loop.
Are the any way of improving this, to bring the time-complexity as close to O(1) as possible?
PS: I'm pretty sure that the the above will never be O(1).
Thank you
c# time-complexity big-o
asked Nov 12 at 15:14
Jaco
61
I would appreciate some feedback with regards to Big-O (time-complexity) of loops, or, ways to improve it.
Let's take the following:
var pairs = 0;
HashSet<int> hs = new HashSet<int>(n);
for (var i = 0; i < ar.Length; i++)
if(!hs.Contains(ar[i]))
hs.Add(ar[i]);
else
pairs++;
hs.Remove(ar[i]);
return pairs;
From what I can determine, the worst-case time-complexity of the above is: O(n), because of the loop.
Are the any way of improving this, to bring the time-complexity as close to O(1) as possible?
PS: I'm pretty sure that the the above will never be O(1).
Thank you
c# time-complexity big-o
c# time-complexity big-o
asked Nov 12 at 15:14
Jaco
61
asked Nov 12 at 15:14
Jaco
61
asked Nov 12 at 15:14
Jaco
61
asked Nov 12 at 15:14
Jaco
61
asked Nov 12 at 15:14
Jaco
61
61
2
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
what isar? alsoif(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.
– styx
Nov 12 at 15:18
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
1
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25
|
show 9 more comments
2
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
what isar? alsoif(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.
– styx
Nov 12 at 15:18
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
1
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25
2
2
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
what is
ar ? also if(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.– styx
Nov 12 at 15:18
what is
ar ? also if(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.– styx
Nov 12 at 15:18
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
1
1
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25
|
show 9 more comments
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%2f53265054%2fimproving-time-complexity%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
active
oldest
votes
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.
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.
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%2f53265054%2fimproving-time-complexity%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
I think you need to be posting your question to codereview.stackexchange.com you also need to provide more clarification as to what your function is trying to achieve
– themehio
Nov 12 at 15:17
what is
ar? alsoif(!hs.Contains(ar[i]))kinda resudent becuase HashSet<T>.Add(T) Method returns true if the element is added to the HashSet<T> object; false if the element is already present.– styx
Nov 12 at 15:18
@styx sorry, ar is an int array.
– Jaco
Nov 12 at 15:22
What exactly are the requirements. It looks like the requirement starts with "look at each element of ar and then..." there is no way to get less than O(n) if you have to look at each element to solve the problem.
– Hogan
Nov 12 at 15:22
1
Think about it this way. Your task is apparently to count pairs in an array -- which you should have said in the question. OK, how would you do that in real life? I take a deck of cards, remove a bunch of the cards, shuffle it, and hand you the cards. Your job is to count the pairs. Obviously you have to look at every card to do that task, so it will be at least O(number of cards)
– Eric Lippert
Nov 12 at 15:25