The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
14 views

Problem with random numbers and while loop [on hold]

I have to generate two random numbers for 52000 instances in an ArrayList, attack 1 and attack 2, where attack 1 must be greater than attack 2, so i have to put them in the list. This is my sample ...
3
votes
1answer
28 views

Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
1
vote
1answer
35 views

Can LOOP-Programm stop when its value goes below 0?

I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$. The definition only says "...
2
votes
1answer
64 views

Proving correctness of an exponentiation routine

I have the following exponentiation routine, which takes $O(\log n)$ steps ...
0
votes
0answers
29 views

Time complexity of nested for loop function involving mod to filter out the execution [duplicate]

I have to find the time complexity of the following program: ...
-2
votes
1answer
66 views

What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
1
vote
0answers
50 views

How to determine big O of a variable loop

I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the ...
8
votes
3answers
298 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
30 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
49 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
46 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
60 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: ...
1
vote
1answer
42 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
61 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
54 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
264 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
86 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
18 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
76 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
140 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
56 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
361 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
305 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
676 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
106 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 (for-...
3
votes
1answer
108 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
386 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
59 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
108 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 $O$...
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
55 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
189 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
61 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
158 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
236 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
96 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
305 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
121 views

Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
0
votes
2answers
126 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
21 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
28 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
345 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
431 views