9 replies to this topic

[toto_7]

I need help to understand how to calculate the time complexity class O() for a function:

int Q (int[]values){

   int len = values.length;

   int res = values[0];

   for (int i =1; i<len; i++){

      if (values[i] > res) res = values[i];

    };

   return res;

}

[lethalwire]

What do you, and don't you understand about measuring the complexity?

[toto_7]

For this function above for example what is time complexity?

[Momerath]

What do you think it is? What variables affect how long it runs? How do they affect the runtime?

[toto_7]

O(N)?

[Alexander]

This appears to be a basis level question, are you taking a class of which teaches this? I would consult your instructor or learning material to the definitions of each of the asymptotic notations and theorize what fits the best one.

I will start you with the most efficient of the pair, constant time, which can be written as O(1).

• An algorithm is said to be constant time if the value of T(n) is bounded by a value that does not depend on the size of the input.
  
• An algorithm is said to be linear time if the value of T(n) is bounded by a value that increases linearly with the size of the input. O(n).

Now these can be said for the algorithm, what about the other steps of function Q? Does that increase the complexity of the function, from just the algorithm alone?

[WingedPanther]

The first thing I would do: pass in a few different sized arrays, and note how many statements are executed, based on each size. Which statements are responsible for the difference in the number of statements executed?

[toto_7]

I think 'for' and 'if' statments are responsible

[Momerath]

Does increasing the size of the array make the if statement take longer to run? Remember to initially look at each line independent of the others.

[toto_7]

I think got the meaning...regardles the array size, if function always executed one time, then is O(1), if time increased as array increased then is O(N) or O(N^2) and so on...