I am doing a question which asks to find the complexity of a nested for loop simplified using big O notation.

The question is:

```
for i <- 1 to n do
for j <- 1 to n do
for k <- 1 to (i+j) do
a unit cost operation
```

I HAVE to prove the above using sum of series notation. I am kind of grasping the concept and have given this a crack. I just want to know whether I am doing it correctly or not.

Here is my answer:

**Assume sum(x=i, y) is the capital sigma notation with x as the lower bound and y as the upper bound.

=> sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1

=> sum(i=1, n) sum(j=1, n) (i+j)

=> sum(i = 1, n) n*i => n * sum (i = 1, n) i

subbing in rule for sum of arithmetic series gives: => n*n/2(n+1) => (n^3 + n^2) / 2

using big Oh rule -> max(f(x), g(x)): => max(n^3/2, n^2/2) => O(n^3)

I know the answer is correct but am not sure if my calculations prior to it are....

With a small correction:

```
sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1
= sum(i=1, n) sum(j=1, n) (i+j)
= [ sum(i=1, n) sum(j=1, n) i ] + [ sum(i=1, n) sum(j=1, n) j ]
= sum(i = 1, n) n*i + sum(i=1, n) n*(n+1)/2
= n * sum (i = 1, n) i + n * n * (n+1) / 2
= n * n * (n+1) / 2 + n * n * (n+1) / 2
= n * n * (n+1)
= n^3 + n^2
= O( max(n^3, n^2) ) <--- as you correctly say
= O(n^3)
```

Actually, it's `Θ(n^3)`

You could also use that `i+j <= 2*n`

:

```
sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1
= sum(i=1, n) sum(j=1, n) (i+j)
<= sum(i=1, n) sum(j=1, n) 2*n
= 2*n * sum(i=1, n) sum(j=1, n) 1
= 2 * n^3
= O(n^3)
```

Straightforwardly and formally (and empirically verified), with `c`

--> *a unit cost operation*:

Similar Questions

I'm reading this Big O article (and some other book references) trying to figure out what changes affect my algorithm. so given the following O(N^2) code: bool ContainsDuplicates(String[] strings) {

Which are the corrent hierarchy between above. is that correct? 0(n^3) < O(2^n) < O(n^2)

I may have the notation wrong. I think this because are not constants ignored in big O notation? I'm pretty new to all this algorithmic analysis stuff. Any help would be greatly appreciated? I'm going

I have a sorted array of doubles (latitudes actually) that relatively uniformally spread out over a range of -10 to -43. Now, if I did a binary search over that list I get O(log N). But, I can further

I've been working through some problems in my textbook that are about calculating the big O complexity of algorithms. One of the questions i'm stumped on doesn't have an answer in the back and i'd app

I'm wondering what is the big O notation for each of the below statement: Sum = 0; for i=1 to N^2 do: for j=1 to N do: 'Sum += 1; Sum = 0 is O(1) for sure, because it will only be executed once. But

I'm having trouble getting my head around algorithm analysis. I seem to be okay identifying linear or squared algorithms but am totally lost with nlogn or logn algorithms, these seem to stem mainly fr

If I have the following code: IterateArray(object[] array) { for(int i=0; i<array.length; i++) { Dosomething(array[i]); } } and the Dosomething(object) method's time performance is O(log n), is th

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 may be teaching a Java crash-course soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the ord

I'm trying to figure out where O(sqrt(n)) and O(n2 log n) fit in this growth hierarchy listed below. This chapter is so confusing and i'm lost on how to figure this out. Any suggestions would be much

I am trying to understand Big-O Notation. So sorry if I am asking something that is too obvious but I can't seem to wrap my head around this. I have the following C# code function that I am trying to

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

int a = 3; while (a <= n) a = a*a; My version is that its complexity is: Is there such a thing?

I'm relatively new to the practice of determining algorithm runtimes using big-O notation and I have a question regarding the runtime of a sorting algorithm. Let's say I have a set of pairs (a, b) in

I've just been introduced to Big-O notation and I've been given some questions. However I'm confused as to how to determine the value of n0. I have to show that 3n^3 +20n^2 + 5 is O(n^3). So far I hav

Hello I am having trouble finding the running time for this algorithm with following assumptions that s = O(logN) and the running time of Random_Integer is constant time: 1 express N-1 as 2^t * u whe

The question asks me to determine the big-O notation for the following efficiencies: 1) 3n3/2 + 3 n1/2 + 10logn + 105n +5 2) 5 n3 +10n2logn 3) 105logn+10n3logn+10n2 4) 3n2+5n3/2 +151logn Here are my

Hi i have started learning algorithm analysis. Here i have a doubt in asymptotic analysis. Let's say i have a function f(n) = 5n^3 + 2n^2 + 23. Now i need to find the Big-Oh, Big-Omega and Theta Notat

I have received the assignment to prove 1/O(n) = Ω(n) However, this would mean that n element of O(n) => 1/n element of Ω(n) which is clearly wrong. So my question is: Is the statement 1/O(n) = Ω(n

Is there any web service to analyze big data sets and plotting graphics like in Excel? I need something simple, efficient and with web GUI.

I'm trying to grasp the idea of Big O for part of a project that is due tonight and I don't know if i'm thinking this through right or not... The project included us writing Iterative and Recursive so

Need some help on solving this runtime recurrence, using Big-Oh: T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2 I don't quite get how to use the Master Theorem here

Possible Duplicate: Big Theta Notation - what exactly does big Theta represent? I understand it in theory, I guess, but what I'm having trouble grasping is the application of the three. In school, w

It seems to be a searching algorithm based off of Mergesort. It is to be used on a sorted array of numbers. Is the Big-O complexity still O(n log n)? public static boolean fastSearch(int[] data, int m

Hi can someone explain me how to resolve this homework? (n + log n)3^n = O((4^n)/n). i think it's the same as resolving this inequality: (n + log n)3^n < c((4^n)/n)). thanks in advance

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

I have read quite a bit on big-O notation and I have a basic understanding. This is a specific question that I hope will help me understand it better. If I have and array of 100 integers (no duplicate

are there a limited amount of basic O Notations, considering you are meant to 'distil' them down to their most important part? O(n^2): O(n): O(1): O(log n) logarithmic O(n!) factorial O(na) polynomia

I have the following question: Solve the recurrence relation simplifying the answer using Big 'O' notation: f(0) = 2 f(n) = 6f(n-1)-5, n>0 I know this is a first order inhomogenous recurrence rela

The following code give me a O(n). how do I code a for loop that has time complexity of O(c^k)? int power(int x, unsigned int y) { if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x

Possible Duplicate: Plain english explanation of Big O I'd imagine this is probably something taught in classes, but as I a self-taught programmer, I've only seen it rarely. I've gathered it is some

I know that the big-o complexity of the following equation is O(n^3) 4n^3 + 6n + 6 because the n^3 is the dominant term. Would the big-o complexity be the same for the same function, but with a nega

Is there a list of the different data structures and their big-O access times for Python? I was rummaging through the standard library docs and didn't see any, hence the question. :-)

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarith

If I want to compute the n-th hexadecimal digit of Pi with http://en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula what is the big O notation http://en.wikipedia.org/wiki/Big_O_notation for the Ba

I am trying to find the Big O for stooge sort. From Wikipedia algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if j - i > 1 then t = (j - i + 1)/3 stoogesort

What wording would be correct to say I can reduce the complexity from O(n^2) to O(n) but reduce in algorithm analysis means you can cast one problem in terms of another for which there exist a known

I have a question about calculating big o notation for the following code: j =1; While (j<=n ) do for i=1 to j do O(1); endfor; j=j*2; endwhile So far, I have that the loop is calculated (sum from

What is O(log* N)? I found it online with no description. edit: I know big-Oh, the log* was the question

i need help finding time complexity of this function in big O notation: int myfunction(bool exists) { int var=0; int k,j,n; if (exists) for(k=1; k<=n; k*=2) for(j=1; j<=k; j++) var++; else for(k

I think this is a simple question, but if I have something like O(n²/2), should I just get rid of the /2 and conclude that O(n²)?

If I have 10 elements and starting with an empty tree, What is the complexity of inserting 10 elements into Red Black in big-O notation? Is it going to be more than O(log 10) because each time it ins

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 was given the following code and was told to find the best and worst case running times in big theta notation. def find(a, target): x = 0 y = len(a) while x < y: m = (x+y)/2 if a[m] < target:

I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets v

why we always consider large value of input in analysis of algorithm for eg:in big-oh notation ?

I am having a hard time understanding Dijkstra's big O notation exactly. I have a question regarding Dijkstra with an unsorted array. As from Wikipedia: The simplest implementation of the Dijkstra's

I may be teaching a Java crash-course soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the ord

There is a LEDA program. http://www.algorithmic-solutions.com/ which basically provides GUI to algorithms. I d like to get into that, I was curious if I can code with C# or JAVA for LEDA. I have look