what would the time complexity of this method be?

Question

What is the time complexity of the following code?

void method1(int n){
  for (int i = 0; i <arr.size()/2; i++){
     System.out.println("");
    }
  }

Interesting that `n` is unused, and `arr` is not defined. – Fred Larson Jul 09 '20 at 18:47 — Fred Larson, Jul 09 '20 at 18:47
let's assume arr is just an array of strings – Anna Jul 09 '20 at 18:49 — Anna, Jul 09 '20 at 18:49
I was thinking it would be o( log(n))? – Anna Jul 09 '20 at 18:49 — Anna, Jul 09 '20 at 18:49

score 1 · Answer 1 · answered Jul 09 '20 at 18:51

Because the number of iterations is proportional to the size of the array, this would be O(n). In general, you'll ignore any constant multiplications on the number of iterations in determining complexity.

You might find this useful: https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html

I'm also guessing that this is a homework problem, so I would encourage you to contact your instructor or TA for additional help. Any good instructor is happy to spend whatever time is necessary to make sure that their students understand the material.

Note that the "n" in `O(n)` would mean `arr.size()`, and not the `int n` parameter. — Fred Larson, Jul 09 '20 at 18:52

score 1 · Answer 2 · answered Jul 09 '20 at 18:53

The complexity of this code depends on the number of time the loop will execute

let's assume the length of arr is m then the loop is going to execute m / 2

But the complexity is not O(m / 2) instead it is O(m) because we drop off constants when finding the complexity.

what would the time complexity of this method be?

2 Answers2