# Tag Info

29

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.

19

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 ...

17

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

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

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

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 ...

10

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 ...

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)$. ...

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 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 ... 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 ... 6 If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically. Some examples: Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable ... 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 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 ofH_n - \ln n$is$\gamma \approx 0.577, which is the Euler-Mascheroni constant. Therefore, we get \begin{align} H_n &... 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 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 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 LetS_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 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 Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested. Another way to derive this ... 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. 4 Translating for-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:$\qquad\displaystyle\begin{align*} \#\mathrm{Task} \quad&= &&\sum_{i=1}^n \sum_{j=1}^{n^2} \sum_{k=1}^j 1 \\ &= && \sum_{i=1}^n \sum_{j=1}^{n^2} j \\ &= && \sum_{...

4

Consider the set of all possible pairs $\langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may not. Basically, the Halting problem asks to create a Turing machine that takes a pair $\langle M, w \rangle$ as input, and eventually halts with answer "YES" if ...

4

Consider the following code snippet: for(int i=0;i<n;i++) The question I have is: whether this loop is executed $n$ times or $(n+1)$ times? This loop executes $n$ times, not $n+1$ times. The first iteration of the loop has $i = 0$; the second has $i = 1$, and so on, up to the last iteration of the loop $i = (n-1)$. Then let us see what happens ...

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