```
void bar(int N){
int c=0;
for (int i=0; i<N*N; i++)
for (int j= i; j< N; j++)
c++;
}
```

The outer (and inner) loops above never get past N. Would this mean the Big O is N*N (N for the outer and N/2 for the inner)?

If you do this

```
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
…
```

you will iterate N times in the inner loop first, then N-1, then N-2, etc., which sums to N(N-1)/2. This loop runs in O(N²), that is the square of the outer loop.

In your case, your code is equivalent to

```
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
c++;
```

since for every positive integer we have N² ≥ N and the compiler should be clever enough to notice that it makes no sense to continue running the outer loop if i is greater than N. So the complexity is indeed O(N²).

If you print `N`

and `c`

after your program runs, you will notice that when `N`

gets doubled, `c`

is almost multiplied by 4 (2²):

```
N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176
```

To know formally the number of iterations and the order of growth:

Similar Questions

can anyone help me verifying the following complexities: 10^12 = O(1)? 2^(n+3) + log(n) = O(2^n)? f(n) = Omega(n) and f(n) = theta(n) <=> f(n) = O(n) thanks

Basically, my question is how nested loops work in netlogo. I've tried nesting two while loops within each other, but the inner one doesn't seem to behave properly (properly being the way they work in

I know that big O notation is a measure of how efficint a function is but I don\t really get how to get calculate it. def method(n) sum = 0 for i in range(85) sum += i * n return sum Would the answe

So, I really don't get Big O notation. I have been tasked with determining O value for this code segment. for (int count =1; count < n; count++) // Runs n times, so linear, or O(N) { int count2

void function(int N){ int c=0; for (int i =0; i< N; i+= N/5) c++; } What is the Big O of the above? Since for every N the loop would iterate 5 times, would it be O(1)?

I have 2 for loops with an operation which would take o(n) inside 1 of the nested for loops. for (i=0;i<someLength;i++){ for(j=i+1;j<someLength;j++){ //some operation requiring O(n) } } What wi

I need to derive the big-O notation of this validation program. Its job is to accept product entries of this type: 'jacket,8,12,18,16,6', validates it, sort the sizes, sort the entry into a list by al

I promise this is the last Big O question Big O Notation for following loops... for (int i = n; i > 0; i = i / 2){ for (int j = 0; j < n; j++){ count++; } } for (int k = 0; k < n; k++){ for

This question already has an answer here: Plain English explanation of Big O 21 answers What is Big O notation? Do you use it? I missed this university class I guess :D Does anyone use it and g

What would be the Big O or Theta of a loop that runs forever? Just curious, was thinking about it today. Could you even bound it?

// n > 0 i ← 0 while (i < n) j ← 0 while (j < power(2,i)) j ← j + 1 done i ← i + 1 done Is the overall complexity O(n(log(n)) because the inner while loop has a conditional where 2^i so 2^0

What is the Big O for the zig-zag merge join algorithm? GAE's Big Table uses it, they go into it in these videos: http://www.youtube.com/watch?v=AgaL6NGpkB8 http://www.bestechvideos.com/tag/zigzag-me

How can I represent the complexity of std::find_end algorithm as Big-O notation? The complexity of std::find_end is defined as follows: At most (last2 - first2) * (last1 - first1 - (last2 - first2) +

Can anyone please let me what would be big O time complexity for the following piece of code: for (int i = 0; i < array.length - 1; i++) { for (int j = i + 1; j < array.length; j++) { // do some

What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

Suppose f(n) is runtime of algorithm. According to function definition of O(n), if f(n)<=c*g(n) then f(n)=O(g(n)) where n0<=n. What is the range of values constant c can take?

I am doing the exercise of Skiena's book on algorithms and I am stuck in this question: I need to calculate the big O of the following algorithm: function mystery() r=0 for i=1 to n-1 do for j=i+1 to

I have been programming in PHP for a long time now, and as I don't come from a computer science / math background I only have a basic understanding of the Big O notation, so I have taken a function an

I am learning algorithm analysis. While doing the theory I across many big-O proofs. I was able to solve them but I need help with omega which is the oposite of big-O? Is 22n = O(2n)? --->My answer

If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is it's O? O(4n^2)? O(n^2)? I know that 7n is cut off, but I don't know if I should keep n^2 coefficient or not. Thanks

I am having some trouble working out the Big O notation for these 2 recursive functions: int calc (int n) { if (n <= 0) return 0 ; else if (n > 10) return n ; else return calc (5 + calc(5n)); }

I wonder whether there is any automatic way of determining (at least roughly) the Big-O time complexity of a given function? If I graphed an O(n) function vs. an O(n lg n) function I think I would be

What is the best way to terminate all nested loops in the example below. Once the if statement is true, I want to terminate the outer for statement (with I). In the other words I need the whole loop t

When I set while1 = false inside of a loop where the value of while1 was true and the loops condition is while(while1) it should exit the loops. In nested if statements it doesn't seem to do this, tho

Possible Duplicate: Big O when adding together different routines What does O(n) + O(log(n)) reduce to? My guess is O(n) but can not give a rigorous reasoning. I understand O(n) + O(1) should reduce

Big O Notation Arrays vs. Linked List insertions: According to academic literature for arrays it is constant O(1) and for Linked Lists it is linear O(n). An array only takes one multiplication and add

I would like to write a function which accepts as input the number of nested loops which the function will perform. For example, if the input parameter is 3, the function will perform 3 nested loops a

JavaScript supports a goto like syntax for breaking out of nested loops. It's not a great idea in general, but it's considered acceptable practice. C# does not directly support the break labelName syn

I am programming in Mathematica and I am trying to avoid multiple for loops. Let n be a given integer and f a function which takes an n-tuple. Given the bound k, I am looking for an efficient way to l

Lets say I have a routine that scans an entire list of n items 3 times, does a sort based on the size, and then bsearches that sorted list n times. The scans are O(n) time, the sort I will call O(n lo

I'm having some trouble with nested loops. Does anyone know a better way of doing this: @product.tracks.each do |t| t.artists_tracks.each do |at| at.role = at.artist.role at.position = at.artist.posit

The code below shows nested while loops, but it's not the very efficient. Suppose I wanted to extend the code to include 100 nested while loops. Is there a better way to accomplish this task? <?php

Does the following code just parallelize the first (outer) loops, or it parallelize the entire nested loops? #pragma omp parallel for for (int i=0;i<N;i++) { for (int j=0;j<M;j++) { //do task(i

I have this program that returns a factorial of N. For example, when entering 4,,, it will give 1! , 2! , 3! How could I convert this to use nested loops? public class OneForLoop { public static void

What in an exact formal manner does the expression f(n) = 2^O(n) mean?

sum = 0; for (i=0;i<n/2;i++) for (j=i; j<n/4; j++) sum++; What is the big O for the above code? I calculated the big O but I'm not sure if it's correct. This is my answer the outer loop will r

There are a lot of questions about big O notation, but I didn't found clear answer for this question. We write that: O(5n) = O(n) and O(3n^2 + n + 2) = O(n^2) Can we write that: O(2^(2n)) = O(2^n)? Th

I want to match the lines of one text file with another text file, line by line, there is a problem with my nested for loops, it must be simple, but I can't find it, for line1 in ratings: cont1+=1 for

Need to take the values from one array, put them through a function and put them in another array. It is meant to be done using a pair of nested for loops. Please help. Complete beginner here. EDIT: O

Possible Duplicate: Breaking out of nested loops in Java How can I use break and/or continue statements to return to the first line of the while loop at points 1, 2 and 3, for example, as indicated

Just wondering if its worth it to make a monolithic loop function or just add loops were they're needed. The big loop option would just be a loop of callbacks that are added dynamically with an add f

I'm trying to understand a particular aspect of Big O analysis in the context of running programs on a PC. Suppose I have an algorithm that has a performance of O(n + 2). Here if n gets really large t

I'm trying to figure out a simple way to handle dynamic nested loops level. Consider the following function that takes in 2 parameters: #num of loops, and max value. void PrintLoop(int maxloop, int ma

Similar to this: http://stackoverflow.com/questions/426878/is-there-any-way-to-do-n-level-nested-loops-in-java I want to create a recursive function, which generates N nested loops, where the indicies

Ok, I am trying to understand the concept of Big O. I have a function I am suppose to find the Big O and I am not quite getting it this is an example in the book of one that is like my homework.. I

I have nested foreach loops in my view, and am having problems with the radio buttons. @foreach (var header in Model.surveyHeaders) { <h1>@header.Name</h1> foreach (var subHeader in Model.

I am trying to run two while loops in parallel for the purpose of data acquisition. This program will run for n num_trials with specific trial duration for each trial. During each trial, the program

Possible Duplicate: are there any O(1/n) algorithms? Is it ever possible for your code to be Big O less than O(1)?

find the big oh characterization input: n s<-0 for i<-1 to n^2 do for j<-1 to i do s<-s+i Both loops iterate n^2 times. I'm not sure if I should add or multiply the loops. Right now I thi

In a beginner's programming book (free licence) there was the following code, dynamically creating nested loops in Java: import java.util.Scanner; public class RecursiveNestedLoops { public static int