Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

4
votes
5answers
2k views

How can a computer run an infinite loop?

I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop ...
0
votes
0answers
18 views

Why the answer is 26 for this code? [migrated]

public class Program { public static void main(String[] args) { int x=1; for(;x<6;x++) x=x*x; System.out.printf("%d",x); } } I ...
0
votes
0answers
28 views

Recursion func to get list of objects

I want to write code that returns a list of $X_i$ values base on this logic. Assuming $X> 1$ a positive non decimal number, and $n$ is the number of objects: $X_n = X-X_1$ $X_i = X_{i+1} / 2$ $...
0
votes
0answers
27 views

Big-O of a recursive function [duplicate]

just wondering, what's the big o of this function, let say the initial value of the parameters is as following: ...
-1
votes
1answer
53 views

Measuring infinite loops [closed]

Theoretically, is there a way to measure how many infinite loops are running at a given point in time? In other words, is there a way to freeze everything and get a number on how many infinite lines ...
-1
votes
1answer
62 views

What is the procedure to find the time complexity of python program? [duplicate]

Is there any kind of function which is used in python to calculate the time complexity of another function?
0
votes
1answer
50 views

How do you solve this [1,5,9,4] pair numbers problem?

So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs ...
1
vote
0answers
15 views

Nested Function stuck on iteration update

I want to solve the Sparse Extended Information Filter Slam described by Dr. Sebestian Thrun in Probabilistic Robotics.I stuck in some nested function. The algorithm is described in page 309 in this ...
0
votes
1answer
33 views

Exponential nested Loop Big O complexity calculation [duplicate]

Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this ...
-1
votes
0answers
30 views

Hard Big O complexity for 3 loops [duplicate]

So this is a tricky one, i try to calculate Big O complexity for this code but I always fail.... I tried to nest SUM's or to get the number of steps for each case like: i=1 j=1 k=1 (1 step) i=2 j=1,...
1
vote
1answer
50 views

What changes do I need to make to my algorithm to make this scene from a different angle? [closed]

The code below is in F#. It creates a scene which looks like a perspective coming from the top left. I thought if I would change i % j = w then it would come from ...
3
votes
0answers
118 views

How Janus (Reversible Programming Language) `if`, `while`, and Update Work

In Reversible Computing, all program statements are reversible. I understand for example that the following: \begin{align} x\ {+}&{=}\ 4\\ y\ {*}&{=}\ x\\ x\ {-}&{=}\ 10 \end{align} Has ...
2
votes
1answer
72 views

Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case? Even in the case of a reversely sorted list, it's not like it'll have ...
0
votes
3answers
33 views

What is the most used way to write for-loop as pseudocode?

for $e\leftarrow1$ to 8 do for $e\in[1,8]$ do for $e\in\{x\in\mathbb{N}|1\le x\le8\}$ do What is more preferred?
0
votes
1answer
68 views
1
vote
1answer
274 views

Runtime analysis of while-loop analysis

s = n while (s > 4) s = s / 2 else s = s - 1 Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs. $S(n)=1 + S(n/2)$ if $n$ is even $S(n)=...
2
votes
1answer
26 views

Big Oh notation for a function with two inputs of linear growth

I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function: ...
1
vote
1answer
37 views

Loop termination - Loop invariant

(x >= 0 && y >= 0) q = 0; r = x; while ( r >=y ) { r = r - y; q = q + 1; } (x = q*y +r) && (r >= 0) && (r < y) For ...
1
vote
0answers
18 views

Scheduling loop

I do not understand how do you write schduled loop from unscheduled one. The unscheduled loop straightforward if you follow the stall rules. The rules say you are supposed to stall after L.D but in ...
-1
votes
1answer
25 views

Little bit confusing to compute time complexity of nested loop [duplicate]

1 for(i=1; i<=n; i++){ 2 for(j=1; j<=n; j*=2){ 3 a[i][j]=b[i][j-1]+1; 4 } 5 } line 1 : n+1 times lnie 2 : n/2+1 times line 3 : constant time c ...
3
votes
1answer
45 views

time complexity when power is involved in iteration

How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * <something>. I ...
1
vote
2answers
195 views

Time complexity of euler totient function

Code for finding $\phi$(n) is ...
1
vote
2answers
202 views

Solving complexity using summation

I have the following algorithm: func() { for(i=1; i<n; i=i*2) print("aa"); } How can I find Big-Oh using summation?
1
vote
1answer
247 views

Complexity of while loop using series

For the following code fragment: i = 1; s = 1; while(s <= n) { i++; s = s+i; printf("x"); } How can we go about proving the time complexity of ...
0
votes
1answer
57 views

Complexity of a loop

If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop? I am trying to figure out the correct answer to this ...
1
vote
1answer
91 views

Run Time of Nested Loop

In the following loop for i = 1 to n doSomething O(1) for j = 1 to k doSomething O(1) Is the runtime still $O(nk)$ even with the expression in ...
0
votes
0answers
63 views

How many operations does this algorithm require?

I have the following algorithm x = 0 S = {} k = 1 while x + a[k] < n do S = S + {k} x = x + a[k] k = k + 1 end where ...
0
votes
1answer
37 views

Loop Transforms to Increase Parallelism

I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm: ...
1
vote
1answer
706 views

Recursion call inside a for loop time

I'm analyzing a piece of code that has a recursive call inside a for loop such as: ...
1
vote
1answer
1k views

Find Number of even subarrays $O(n)$ [explanation needed]

So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must ...
0
votes
0answers
27 views

Conditions for arrays allowing load forwarding and load bypassing

Given following instruction sequence that corresponds to the operation Y(i) = A * X(i) + Y(i): ...
1
vote
1answer
190 views

How to get Loop invariants to prove program is correct in Hoare logic

start off stating the definition of a loop invariant. It is a condition that must be true at the start of the loop and must be true after each iteration of the loop. I understand what it is but i have ...
0
votes
0answers
10 views

Function complexity [duplicate]

I'm trying to get upper bound of my function. The complexity of vector::erase - O(n), so I think that my upper bound - O(n^3), Is it true? ...
0
votes
2answers
226 views

what is halting problem? [duplicate]

i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure ...
0
votes
0answers
83 views

Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...
-2
votes
1answer
153 views

How to get O(Big-oh) notation for following Code [duplicate]

What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore 2log n times it will execute 2) outer goes to n incrementing by 1 threfore n times Hence for ...
1
vote
0answers
44 views

Hoare correctness proof for a recursive definition of multiplication

Given the program: {y=y0 ^ y>=0} z=0; while (y>0){ z=z+x; (1) y=y-1; } {z=x*y0} I am having trouble finding the ...
1
vote
1answer
69 views

Maximum value of LOOP-Program turing-computable

Lets consider the class of "simple" LOOP-Programs. A LOOP-Program P is inducively defined as: $P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$ ...
2
votes
1answer
140 views

What is more effective, a do while or a while?

I mean, with the same code, if I modify a do while into a while in this way: do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change in the code? B = condition S; = instructions
1
vote
0answers
40 views

Time complexity of a nested loop [duplicate]

I need to figure out the complexity of the following loop in theta notation but I can't figure it out. Some help would be much appreciated. ...
1
vote
3answers
791 views

Nested Loop Time Complexity vs Successive Loops

An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic ...
0
votes
1answer
93 views

Construct a loop program for equality

I want to construct a loop-computable program for this construction: IF x1 = c THEN P ELSE P' I know how to transform if else construction in loop , but I can't understand how to check the equality....
2
votes
1answer
238 views

How can I convert a for loop to a recursive function?

My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b. This is what I created: ...
1
vote
1answer
120 views

Calculate the complexity of an algorithm [duplicate]

I have an algorithm here and it wants me to calculate the complexity: ...
2
votes
2answers
144 views

When are range-based for loops better than regular for loops? [closed]

Is it when you need faster performance, to iterate over a container, or when you don't need an index variable? From my understanding it should be when you need to iterate over a container. Am I ...
0
votes
0answers
230 views

How to calculate runtime complexity of the nested loops with variable length

Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s character. The algorithm will ...
1
vote
2answers
168 views

Complexity of the algorithm to find occurences of a given number in a given array

I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm: ...
2
votes
1answer
296 views

Time complexity of nested loops help [duplicate]

How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone ...
1
vote
0answers
57 views

Big-Oh of algorithm

I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345. The algorithm looks like: ...