# Tag Info

30

In a contemporary processor there is, among many other things, a register (digital electronic component to hold some bits) called the Program Counter (PC). It holds the memory address to the current machine instruction. During normal flow of the program, the PC will always be updated to address the next instruction. However, any loop will be implemented ...

26

step 1: take a calculator step 2: input a number step 3: add 1 to the number step 4: subtract 1 from the number step 5: goto step 3 If you didn't eventually get tired or bored you would be switching between the 2 results forever. Computers don't get tired or bored.

17

The reason that loops are faster than recursion is easy. A loop looks like this in assembly. mov loopcounter,i dowork:/do work dec loopcounter jmp_if_not_zero dowork A single conditional jump and some bookkeeping for the loop counter. Recursion (when it isn't or cannot be optimized by the compiler) looks like this: start_subroutine: pop parameter1 pop ...

16

These other answers are somewhat misleading. I agree that they state implementation details that can explain this disparity, but they overstate the case. As correctly suggested by jmite, they are implementation-oriented toward broken implementations of function calls/recursion. Many languages implement loops via recursion, so loops are clearly not going ...

11

Instead of a general "formula", you should try to work out from principles first, at least in the beginning. You can see that the number of executions are: $$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1$$ We try solving them one step at a time. The innermost (right-most) summation can be solved as: \sum\limits_{k=j}^{i} 1 = i - j +... 11 We have lots of questions about the time complexity of sums, and the answer is the same every time: Loops translate to sums.¹ Every other shortcut will get you into trouble. In your case, you seem to have identified statement1 as (dominant) operation you want to count. So your nested loop for ( i=1; i<n; i++ ) { for ( j=1; j<=i; j++ ) { ... 10 The result is correct, but your reasoning is not. You can't mix big-oh with ellipses. It happens to work here because of extra conditions that happen to be true but that you haven't checked. Why summing big-ohs just doesn't work Fundamentally, you are abusing notation. For example, it doesn't make much sense to write O(1), O(2), O(3), etc. as if they ... 10 I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply. do-while is equivalent to while-do. do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y). Life is a bit ... 9 Let's assume that adding two strings of lengths a,b takes time a+b. Consider the following strategy to convert a list of n characters into a list: Read the list in chunks of k, convert them to strings, and sum the chunks. Creating each chunk takes time \Theta(1+2+\cdots+k) = \Theta(k^2), and we do this n/k times, for a total of \Theta(nk). ... 9 AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be calculated (or variables depending on them). Here is an example: if x = 3 then 9 else x * x At close inspection you will recognize that the above is really just ... 7 Just a hint for now, since this is a practice problem: consider a lexicographic combination of orders. In some more detail: Suppose you have two maps f_1:S\to D_1 and f_2:S\to D_2 from your program states S into well-founded ordered domains (D_1,\le_1) and (D_2,\le_2). The lexicographic combination of \le_1 and \le_2 is the order \le on ... 6 When you are using vectorized operations in a high-level language such as Matlab or python, you are not avoiding loops, but rather pushing them from the high-level language (Matlab or python) to a low-level language (C or fortran) which can execute these loops much faster. Loops in Matlab or python are slow for several reasons, the main ones being that these ... 6 At the most basic level, an "infinite loop" only requires two transistors — an astable multivibrator will alternate between two different digital states indefinitely as long as it has power. In some sense, every other loop is just a bigger version of this. You don't need more and more transistors to keep operating for a longer period of time. But what you ... 5 So I managed to solve this issue today. The code for my while loop: while (condition: ~>bool) (body: ~>void) => void { if condition { body; while condition body; }; } When I go to build this into CIL (a stack based runtime, important for the psuedocode, not important for the answer) it looks like: ldarg 0 <build ... 5 The n^{th} harmonic number can be approximated by the integral \int_1^n \frac{1}{x} \mathrm{d}x. \begin{align} H_n \approx \int_1^n \frac{1}{x} \mathrm{d}x = \left[ \ln x \right]_1^n = \ln n - \ln 1 = \ln n \end{align} The limit of H_n - \ln n is \gamma \approx 0.577, which is the Euler-Mascheroni constant. Therefore, we get \begin{align} H_n &... 5 What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like: while(i<n){ if(cond) //something Θ(1) else //some other Θ(1) thing i++ } Notice in your case, you have the same variable for both loops with no reset. So, to answer your question, the running time is \Theta(n). In ... 5 For one of the loops, you've a complexity of O(\sqrt n). You're nesting the loops three times, so you'll get the complexity of O(\sqrt n^3), which is O(n^{3/2}). If you want to be more precise, then for your original question, the complexity will be: O(\sqrt n) for the first loop O(\sqrt n - 1) for the second loop, which is the same as O(\sqrt n)... 5 I think you're missing the notion of continuation. Although your compiler may not rely on that notion, as a compiler designer with a functional language as source or intermediate (or target) language, it's important to understand that notion and keep this in mind. The continuation of a piece of code describes what the code exits to. In imperative terms, it ... 5 In a nutshell: What your teacher probably meant is that the semantics of while is pretty much the same in most languages, while the semantics of for may change considerably (see discussion below). Hence, abstract language independent proof are more reliable with a while, but one should be careful that a proof with a for loop may not match the semantics of ... 5 Without fully answering your question, I would like to answer it at least partially by remarking that computation cost can be evaluated only with respect to an abstract model of computation. If you want to use two different models, for two different programs, than you have to determine the complexity of reducing each model to the other, in order to have a ... 5 The answer will depend on the compiler. As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code." In particular, good compilers will do tail-call elimination. In some cases this can effectively transform the code into a for-loop. Your example looks like a good example of an instance where this could happen. As @... 5 If you want the derivative everywhere, automatic differentiation can't handle branches and loops. If you are satisfied with getting the derivative "almost everywhere", automatic differentiation might be fine for some programs with (some kinds of) branches. For some kinds of optimization, this is sometimes good enough. Automatic differentiation can support ... 5 Let S_i be the sum of the array upto index i. Then we can directly calculate the sum of any contiguous subarray x_i, x_{i+1}, ..., x_{j} using the expression S_j - S_{i-1}. This subarray will have even sum only if S_{i-1} and S_j are both even or both odd. With this in mind, we can count how many even and odd S_i we have and then calculate ... 5 You only need two transistors for that, as demonstrated by the old joke. How do you keep a (insert ethnicity here) busy forever? Write "Please turn over" on both sides of a sheet of paper. It's as true for transistors as for humans with a sheet of paper. In this case, two transistors make a bistable oscillator, and they'll toggle between true and false ... 4 Your intuition is correct, the work is in identifying the things you're adding together. The first bit is that printing a string of length m takes m operations, so the System.out.println(input.substring(i,j)); line takes j-i operations. (A side note here is that this code is in Java, unless I'm very much mistaken, and the substring(start, end) ... 4 You need to solve simple formula \sum_{i=1}^N\sum_{j=1}^i\sum_{k=i}^j1 this will give you overall result of \frac{1}{6}N(N+1)(N+2) Math is easy to do here but I used Wolfram Alpha 4 Since you are only interested in the time complexity and can ignore a constant factor of two: Replace 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ... with 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + 1/16 ... for a lower bound, and with 1 + 1/2 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 ... for an upper bound. Then add the ... 4 To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also? The answers to both questions depend on the machine model. In common ones, like e.g. the RAM model, writing every memory cell take a constant amount of time c. Hence, intializing an ... 4 In Python, range(0,n) iterates through the values 0, 1, 2, .., n-1 (but not n). Therefore, your summation should have been\sum_{i=0}^{n-1} \cdots$$rather than$$\sum_{i=1}^{n} \cdots and similarly for the other sums as well.

3

The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky math to figure out exactly how many times the loop is run, but you can know exactly how many times it is run. The first hint that this is $O(1)$ is that there ...

Only top voted, non community-wiki answers of a minimum length are eligible