posted 1 year ago

What your study material says about that?

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?

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?

*[edit] I see OP changed his code, so then we talk about the simple scenario I have mentioned at the end of post.*
posted 1 year ago

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 wrote:0(n)?

No.

Daniel Martos

Ranch Hand

Posts: 126

1

posted 1 year ago

0(1) because it is constant then?

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?

posted 1 year ago

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 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.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Daniel Martos

Ranch Hand

Posts: 126

1

posted 1 year ago

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 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.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Daniel Martos

Ranch Hand

Posts: 126

1

posted 1 year ago

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 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)

posted 1 year ago

You would have gotten extra credit if you mentioned "quadratic" but that's good enough.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

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