The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
1answer
33 views

Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
3
votes
0answers
25 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
2
votes
1answer
47 views

Costs of updating arrays to contain only zeroes

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? And in that case, ...
1
vote
2answers
38 views
0
votes
0answers
31 views

Frequency count of while loop [duplicate]

I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count ...
3
votes
1answer
57 views

Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation: ...
-3
votes
0answers
9 views

big o complexity analysis of dependent nested loops [duplicate]

for(i=0;i<=n;i++) { for(j=0;j please help me in finding complexity of this nested loop.... the outer loop is executing n times and inner loop is dependent on the value of i. so what will be its ...
1
vote
1answer
41 views

Runtime of algorithem when the internal for depend on the external for

I'm trying to find the running time of this pseodocose: int x=0,i,j for (i=1;i<=n;i++) for(j=1;j<=n+r;j=j+i) x=x+j; What I did: First I checked ...
0
votes
2answers
52 views

Running-time cost of Tweaked Nested Loop

I understand that the following nested for-loop: for(i=0; i<n/2; i++) for(j=0; j<n/2; j++) print(j) has the runtime complexity of which ...
-1
votes
1answer
47 views

Proving correctness of a loop that calculates the sum of array

I am trying to mathematically prove that the following program is correct: ...
5
votes
1answer
257 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
2
votes
2answers
76 views

Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
2
votes
0answers
17 views

What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
2
votes
1answer
66 views

Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
2
votes
0answers
68 views

How can I use nested loops to print out this triangle word pattern? [closed]

I'm trying to make a pattern that looks like this: And am given this code to start: ...
7
votes
2answers
132 views

Loop variant for a while loop that occasionally doesn't decrease?

I'm working on practice problems for a test I have, and every example of loop variant decreased with every iteration of the loop. On this one, the values remain the same when a < b. My attempts ...
-1
votes
1answer
53 views
0
votes
1answer
39 views

run time analysis of a for loop [duplicate]

I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me. the loop is ...
15
votes
1answer
346 views

Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
2
votes
5answers
297 views

Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
4
votes
4answers
670 views

Loops at low level

When programming with high level languages like Python or Matlab, it is always better to model the problem such as the solution is some kind of vector or matrix multiplication, to avoid loops. But ...
0
votes
1answer
102 views

Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural ...
3
votes
1answer
98 views

Running time function for an algorithm with while and for loop

I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and ...
1
vote
1answer
381 views

provability of while loop vs for loop [closed]

I'm abit afraid to ask this question here seeing as I asked it on programmers SE already, the thing is I think the question is more about the underlying theory than the use in practice (or call it ...
0
votes
1answer
57 views

Algorithm analysis of nested loop [duplicate]

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
2
votes
1answer
96 views

Simplifying a nested sum

I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big ...
0
votes
0answers
15 views

Runtime of this loop [duplicate]

I need some advice on how to determine the runtime of this loop : s=0 for ( i=1 , i <= 2^m ; i=i*2 ) { s++ } return s With $C_1$ = actions ...
-1
votes
1answer
53 views

What is the time complexity (big O) of this nested for-loop? [duplicate]

What is the time complexity (big O) of this nested for-loop? I believe it's either O(n) or O(n^2) ...
0
votes
1answer
176 views

Finding a Hoare logic correctness proof for a Repeat-Until loop

How can we prove a program in repeat until using Hoare Logic? I've found a rule like this: {P} S {R}, {R ^ ~B -> P}, {R ^ B -> Q} for ...
0
votes
0answers
17 views

Confusion with space and time usage [duplicate]

The following is my own set-up code: ...
1
vote
1answer
60 views

Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
4
votes
2answers
152 views

How to bridge theory and implementation for while loops?

I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - ...
-2
votes
1answer
225 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
0
votes
0answers
23 views

Nested Loop Complexity [duplicate]

I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj). The lists are all sorted. My aim is to iterate through the list and match 1 or ...
1
vote
1answer
89 views

Loop invariant: decreasing a variable and swapping it

As an example exercise, we were asked to find the loop invariant for this bit of code. ...
-1
votes
1answer
296 views

Runtime of nested loops

What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case. ...
0
votes
0answers
17 views

Big o notation for the algo [duplicate]

Asked this at programmers Stack Exchange, was recommend to ask here : What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) ...
0
votes
1answer
118 views

Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
0
votes
2answers
125 views

What is the Big O estimate of a nested for loop?

I am trying to figure out what the big o estimate of the following for loop is. ...
0
votes
0answers
20 views

Time complexity of complex nested for loops [duplicate]

What are the time complexities of the following code? I posted this on the general stackexchange website, but it was suggested that I post it here. ...
1
vote
0answers
27 views

Complexity of a nested for loop [duplicate]

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows: What value is returned by the following function? Express your ...
0
votes
3answers
328 views

Calculating time complexity of two interdependent nested for loops

Consider the following code segment : for (int i = 1; i <= n; i++ ) { for (int j = 1; j <= n; j = j + i ) { printf("Hi"); } } Here, the ...
0
votes
2answers
43 views

make Magic Square? [closed]

I need to write a function that takes in a 2D list, that is a NEARLY magic square, meaning that if you perform ONE swap, it becomes a magic square. The function would take in this nearly magic square, ...
1
vote
1answer
428 views
1
vote
1answer
610 views

Sum number of times statement is executed in triple nested loop

I have this code fragment: for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) for( k=0; k<j; k++ ) S; I need to find the number of times ...
5
votes
3answers
3k views

What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
3
votes
1answer
269 views

Theta Runtime of Nested for Loops

I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much ...
1
vote
1answer
216 views

Can a Turing machine decide if a LOOP program stops for the integer input 0

This is a question I found in a practice exam while I am preparing for my mid term exam. The answer needs justification, either a pseudo code or a logical explanation why not. What puzzled me about ...
1
vote
1answer
164 views

Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra

Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs? Long version and some background: Before ...
0
votes
1answer
87 views

Confusion related to calculating time complexity

I have some confusion related to calculating the time complexity of this algorithm opt(i) for j=i:n a = f(i,j) + opt(j+1) end How is the running ...