The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
49 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
15 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
23 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
2answers
77 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
26 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
193 views

Bubble sort complexity

So I have this code: ...
1
vote
1answer
160 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 ...
3
votes
3answers
262 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
136 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
89 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
62 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
81 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 ...
2
votes
2answers
226 views

Analyzing programs with multiple for-loops

If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these... the ones like ...
1
vote
1answer
1k views

Triple nested for-loops [duplicate]

Possible Duplicate: A puzzle related to nested loops I am trying to count the exact/total number of iterations the following nested for-loops are executed: ...
0
votes
2answers
196 views

A puzzle related to nested loops

For a given input $N$, how many times does the enclosed statement executes? for $i$ in $1\ldots N$ loop $\quad$for $j$ in $1\ldots i$ loop $\quad$$\quad$for $k$ in $i\ldots j$ loop ...
2
votes
2answers
520 views

Runtime analysis of a nested loop

I have some difficulties performing the worst case analysis on this algorithm. The outermost loop is executed $2N$ times. The while loop, in the worst case, will increase by $2$ each time, so it ...
1
vote
1answer
258 views

Asymptotic time complexity of a two-loop program

I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for: ...