Algorithm complexity with iterations. Is it logarithmic or exponential?Big O, how do you calculate/approximate it?Improve INSERT-per-second performance of SQLite?Time complexity of a recursive algorithmSpeed comparison with Project Euler: C vs Python vs Erlang vs HaskellWhat does the C ??!??! operator do?How to find time complexity of an algorithmThe time complexity of the leader-follower algorithm?How is the complexity of this algorithm logarithmic?Time complexity of iterative and recursive algorithmsCalculating the time complexity of recursive algorithm T(n) = T(k) + T(n-k)Why is the time complexity of this algorithm exponential?
Size of electromagnet needed to replicate Earth's magnetic field
Why must Chinese maps be obfuscated?
Get consecutive integer number ranges from list of int
Pre-plastic human skin alternative
Does Gita support doctrine of eternal samsara?
Apply MapThread to all but one variable
What makes accurate emulation of old systems a difficult task?
Aliens crash on Earth and go into stasis to wait for technology to fix their ship
Extension of 2-adic valuation to the real numbers
Multiple options vs single option UI
Why didn't the Space Shuttle bounce back into space as many times as possible so as to lose a lot of kinetic energy up there?
How to pronounce 'c++' in Spanish
Can someone publish a story that happened to you?
Solving polynominals equations (relationship of roots)
On The Origin of Dissonant Chords
Do I have an "anti-research" personality?
How can I practically buy stocks?
Was Dennis Ritchie being too modest in this quote about C and Pascal?
What happens to Mjolnir (Thor's hammer) at the end of Endgame?
What's the polite way to say "I need to urinate"?
Is there really no use for MD5 anymore?
How to limit Drive Letters Windows assigns to new removable USB drives
How could Tony Stark make this in Endgame?
"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?
Algorithm complexity with iterations. Is it logarithmic or exponential?
Big O, how do you calculate/approximate it?Improve INSERT-per-second performance of SQLite?Time complexity of a recursive algorithmSpeed comparison with Project Euler: C vs Python vs Erlang vs HaskellWhat does the C ??!??! operator do?How to find time complexity of an algorithmThe time complexity of the leader-follower algorithm?How is the complexity of this algorithm logarithmic?Time complexity of iterative and recursive algorithmsCalculating the time complexity of recursive algorithm T(n) = T(k) + T(n-k)Why is the time complexity of this algorithm exponential?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
If I have the following algorithm
for (i = 1; i <= 4 * n; i = i * 4)
for (k = 1; k < 1000; k = 2 * k)
print(k);
print(i);
how can I calculate its complexity?
I only understand that for one iteration of for(i=1; i≤4n; i=i*4), the line with print(i) is O(1), and for one iteration of for(k=1; k<1000; k=2*k), the line with print(k) is O(1).
I'm not sure how to proceed.
c time-complexity
edited Mar 22 at 22:31
chqrlie
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
add a comment |
If I have the following algorithm
for (i = 1; i <= 4 * n; i = i * 4)
for (k = 1; k < 1000; k = 2 * k)
print(k);
print(i);
how can I calculate its complexity?
I only understand that for one iteration of for(i=1; i≤4n; i=i*4), the line with print(i) is O(1), and for one iteration of for(k=1; k<1000; k=2*k), the line with print(k) is O(1).
I'm not sure how to proceed.
c time-complexity
edited Mar 22 at 22:31
chqrlie
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56
add a comment |
If I have the following algorithm
for (i = 1; i <= 4 * n; i = i * 4)
for (k = 1; k < 1000; k = 2 * k)
print(k);
print(i);
how can I calculate its complexity?
I only understand that for one iteration of for(i=1; i≤4n; i=i*4), the line with print(i) is O(1), and for one iteration of for(k=1; k<1000; k=2*k), the line with print(k) is O(1).
I'm not sure how to proceed.
c time-complexity
edited Mar 22 at 22:31
chqrlie
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
If I have the following algorithm
for (i = 1; i <= 4 * n; i = i * 4)
for (k = 1; k < 1000; k = 2 * k)
print(k);
print(i);
how can I calculate its complexity?
I only understand that for one iteration of for(i=1; i≤4n; i=i*4), the line with print(i) is O(1), and for one iteration of for(k=1; k<1000; k=2*k), the line with print(k) is O(1).
I'm not sure how to proceed.
c time-complexity
c time-complexity
edited Mar 22 at 22:31
chqrlie
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
edited Mar 22 at 22:31
chqrlie
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
edited Mar 22 at 22:31
chqrlie
64.3k852108
edited Mar 22 at 22:31
chqrlie
64.3k852108
edited Mar 22 at 22:31
chqrlie
64.3k852108
64.3k852108
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
asked Mar 22 at 17:40
Rosario Di PalmaRosario Di Palma
31
31
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56
add a comment |
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56
add a comment |
1 Answer
1
active
oldest
votes
Here's the inner loop:
for(k=1; k<1000; k=2*k)
print(k);
That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ 1,2,4,8,16,32,64,128,256,512.
The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.
Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
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%2f55305114%2falgorithm-complexity-with-iterations-is-it-logarithmic-or-exponential%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Here's the inner loop:
for(k=1; k<1000; k=2*k)
print(k);
That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ 1,2,4,8,16,32,64,128,256,512.
The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.
Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
add a comment |
Here's the inner loop:
for(k=1; k<1000; k=2*k)
print(k);
That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ 1,2,4,8,16,32,64,128,256,512.
The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.
Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
add a comment |
Here's the inner loop:
for(k=1; k<1000; k=2*k)
print(k);
That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ 1,2,4,8,16,32,64,128,256,512.
The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.
Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
Here's the inner loop:
for(k=1; k<1000; k=2*k)
print(k);
That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ 1,2,4,8,16,32,64,128,256,512.
The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.
Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
answered Mar 22 at 17:48
rob mayoffrob mayoff
298k43601648
298k43601648
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.
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%2f55305114%2falgorithm-complexity-with-iterations-is-it-logarithmic-or-exponential%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
Possible duplicate of Big O, how do you calculate/approximate it?
– Prune
Mar 22 at 21:44
If you search on the phrase "determine computational complexity" or any reference on SO, you’ll find resources that can explain it much better than we can in an answer here.
– Prune
Mar 22 at 21:56