programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Complexity

Ranch Hand
Posts: 126
1
Using the Big O notation and N, how does one go about finding the complexity of such a method?

author
Sheriff
Posts: 23295
125

First of all, the code won't compile, because you have commas instead of semi-colons. Second, assuming that you fix the syntax errors, the inner loop is an infinite loop because you used the wrong index variable.

Henry

Daniel Martos
Ranch Hand
Posts: 126
1
Ok, sorry

Sheriff
Posts: 4931
334

Well, the algorithm's complexity determines the runtime rate growth as the input size grows. You have mentioned N, so what it represents? It represents your input, which is an array, more presicely - its size, even more precisely and in Java terminology, that would be length. So you always need to consider the worst case scenario the algorithm could run with a given input.

Look at this example
Such algorithms complexity would be O(n) as in its worth case scenario loop would iterate N times. In different words, not known exact times of iteration.

If you were have a loop
Its complexity would be O(1) as your loop would iterate maximum 4 times, which is a known value to you and any other input doesn't affect its iteration number. So we say algorithm runs at constant time.

Now if you were have for instance
Such algorithm also would be considered to run at constant time, which is O(1), as regardless of the input size (once again - array), your loop would run at most 5 times.

Now about your particular case. Note, it wouldn't look tricky at all, if nested (or inner) loop iteration counter would be "k < value.length" there, but it isn't, it is "i < value.length", so here I think you got a doubt, as it isn't a classical easily recognizable example with two nested loops and its coplexity O(n*n). However, if you'd look further (by the way, there is a good book Introduction to Algorithms)
So lets take it out loud. Outer loop will iterate N times. Inner loop every time will shrink depending on outer loops value of i (as it increases each iteration), so that would look similarly (as iterations progress) to N + N-1 + N-2... and so on. Remember, that precise runtime is very difficult to obtain and in fact it is not needed. You always take the worst case scenario, which is the same as?

 I see OP changed his code, so then we talk about the simple scenario I have mentioned at the end of post.

Daniel Martos
Ranch Hand
Posts: 126
1
0(n)?

Liutauras Vilda
Sheriff
Posts: 4931
334
Daniel Martos wrote:0(n)?

No.

Regardless of your changes in code (initial post vs latter), complexity of those two algorithms is the same.. Henry pointed out the mistake in there, so first version is infinite. I was having in mind version where inner's loop index is 'k = i + 1' and this is what I thought you had in mind.

Daniel Martos
Ranch Hand
Posts: 126
1
Liutauras Vilda wrote:
Daniel Martos wrote:0(n)?

No.

Regardless of your changes in code (initial post vs latter), complexity of those two algorithms is the same.. Henry pointed out the mistake in there, so first version is infinite. I was having in mind version where inner's loop index is 'k = i + 1' and this is what I thought you had in mind.

0(1) because it is constant then?

Sheriff
Posts: 11494
180
Daniel Martos wrote:0(1) because it is constant then?

O(1) is practically instantaneous (edit: relative to say O(n) and O(n^2)), worst case. That's about as good as anything will ever get.  You'll never get that kind of O from a nested for loop.

Daniel Martos
Ranch Hand
Posts: 126
1
Junilu Lacar wrote:
Daniel Martos wrote:0(1) because it is constant then?

O(1) is practically instantaneous, worst case. That's about as good as anything will ever get.  You'll never get that kind of O from a nested for loop.

O(Nsquared)?

Junilu Lacar
Sheriff
Posts: 11494
180
Daniel Martos wrote:O(Nsquared)?

My instructors in school always insisted we show our solution. You've gone from O(n) to O(1) to O(n^2). All of these looked like guesses. The trick to learning this concept is knowing how to get there, not the final answer. So, show your solution.

Daniel Martos
Ranch Hand
Posts: 126
1
Junilu Lacar wrote:
Daniel Martos wrote:O(Nsquared)?

My instructors in school always insisted we show our solution. You've gone from O(n) to O(1) to O(n^2). All of these looked like guesses. The trick to learning this concept is knowing how to get there, not the final answer. So, show your solution.

the outer loop executes N times,
the inner loop also executes N times,
so it would be O(N * N) or O(n^2)

Junilu Lacar
Sheriff
Posts: 11494
180
You would have gotten extra credit if you mentioned "quadratic" but that's good enough.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.