All Questions

Filter by
Sorted by
Tagged with
2
votes
1answer
62 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
3answers
924 views

Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
0
votes
0answers
32 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
99 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
53 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
521 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 has ...
3
votes
2answers
2k 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
20 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. ...
0
votes
1answer
898 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 ...
1
vote
1answer
429 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
760 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 ...
2
votes
1answer
626 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
16 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
229 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
0answers
17 views

Confusion with space and time usage [duplicate]

The following is my own set-up code: ...
1
vote
1answer
272 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): ...
-2
votes
1answer
838 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
31 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
421 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. ...
0
votes
0answers
18 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
235 views

Understanding the time-complexity of Insertion Sort

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below). ...
1
vote
1answer
2k views

Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
2
votes
1answer
137 views

Nested loops: Still $\mathcal O(n)$?

I have an algorithm similar to this: i=1 while(i < n) { //something in O(1) while(i < n && cond) { //something in O(1) i++ } i++ } ...
0
votes
0answers
59 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
252 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 ...
0
votes
3answers
930 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 ...
1
vote
1answer
785 views

Bubble sort complexity [duplicate]

So I have this code: ...
6
votes
3answers
20k 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
966 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 <...
0
votes
1answer
104 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 ...
4
votes
2answers
1k 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 <...
0
votes
2answers
556 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 $\quad$$...
1
vote
2answers
2k 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 ...
4
votes
2answers
9k views

Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
2
votes
1answer
3k views

Time complexity of a triple nested loop with squared indices

I have seen this function in past year exam paper. ...

1
2