Java – compute Big-O complexity
I'll eventually give the program an input file similar to 60000 400 pixel images, so I'll try to think about how the code runs with large input For ease of reading, I replaced unimportant things with "blah" and all ArrayList names with simple letters (NN, mm and KK)
for (Perceptron P : nn){ //blah } for (Perceptron P : mm) { //blah } for (Perceptron P : kk){ //blah } for (Perceptron P : mm) { for (int i = 0; i < nn; i++) { //blah } for (int j = 0; j < kk; j++){ //blah } } for (Perceptron X : nn){ for (Perceptron Y : mm){ //blah } } for (Perceptron Z : kk){ for (Perceptron Y : mm){ //blah } }
I think the answer is O (NN mm KK mm (NN KK) nnmm kkmm) If I know that NN is 400, mm is 300 and KK is 10, then this is O (246710) But now I'm stuck I really don't know what o (246710) means Do I have to calculate Big-O for only one variable at a time? If so, what are the benefits? I just want to know how this will behave thank you
Solution
Big-O only involves the largest item in the running time, in this case o (mm * (NN KK)) The part of the code that generates this term is the following nested loop:
for (Perceptron P : mm) { for (int i = 0; i < nn; i++) { //blah } for (int j = 0; j < kk; j++){ //blah } }
If you tell us the relationship between KK, mm and NN and the actual size of the image, we can limit your running time in more meaningful terms