Program complexity
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 1 more comment
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 7 at 19:00
David G. Stork
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 7 at 19:00
David G. Stork
10.2k21332
edited Jan 7 at 19:00
David G. Stork
10.2k21332
edited Jan 7 at 19:00
David G. Stork
10.2k21332
10.2k21332
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
1
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Dzaroslaw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Dzaroslaw is a new contributor. Be nice, and check out our Code of Conduct.
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%2fmath.stackexchange.com%2fquestions%2f3065354%2fprogram-complexity%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
Dzaroslaw is a new contributor. Be nice, and check out our Code of Conduct.
Dzaroslaw is a new contributor. Be nice, and check out our Code of Conduct.
Dzaroslaw is a new contributor. Be nice, and check out our Code of Conduct.
Dzaroslaw is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3065354%2fprogram-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
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11