Complexity in terms of Θ

Question

I know that the following code is considered "Linear or Θ(n)" what I don't understand is how we know that it is.

Assuming that n has been declared appropriately and has been set to a value.

int sum = 0;
for (int i = 0; i < n*2; i++ )
   sum++;

Below is an additional loop that is non-linear from what I can tell but again my question is how do we determine possible speeds by seeing only code? Θ complexity, in terms of n, to be more specific.

int sum = 0;
for ( int i = 0; i < n; i++)
   for ( int j = i; j < n; j += 2)
      sum++;

Count how many times the `sum++` statement will execute for different values of `n`. — Patricia Shanahan, Mar 04 '15 at 02:01
well technically @MitchWheat is correct since he swapped Θ to O — Mateusz Dymczyk, Mar 04 '15 at 02:12
@ user4098326: I mistook the multiply for 'power of'. I shall slink away in shame... — Mitch Wheat, Mar 04 '15 at 02:46

score 1 · Accepted Answer · edited May 23 '17 at 12:12

In your first example you have only one for loop. The i value linearly increases until the condition i<n*2; is met. The execution time of your for loop is linearly dependent on the value of n so its time complexity is O(n) because your i value is directly proportional to n.

In your second example you have nested for loops. The i value is linearly increasing and for each i value the inner for loop executes n/2 times as your variable j is increased by 2 in each iteration. As the outer loop executes n times and inner loop executes n/2 times for each outer loop iteration, the total running time for this example is n*n/2. But usually the constant part of the time is negligible (or sometimes not considered). So we can say its running time is O(n^2).

Coming to the difference of Big O and Theta notation, Big O is used to represent the upper bound for the growth function and Theta is used to represent the tight bound for the growth function. For more info on the difference, refer difference between Big O and Theta notation.

to be precise he's asking about Θ not O – Mateusz Dymczyk Mar 04 '15 at 02:12 — Mateusz Dymczyk, Mar 04 '15 at 02:12

score 0 · Answer 2 · answered Mar 04 '15 at 02:09

Big O notion can be thought of as given input of size n how many times are each element processed/accessed in the following program?

So for your first example

int sum = 0;
   for (int i = 0; i < n*2; i++ )
      sum++;

It doesn't matter what size n is. It only matters how many times does the loop run in respect to n. So since this piece of code will loop n*2 times, the running time of it is also n*2. The reason that this is called linear, or O(n) even though it will run n*2 times is because we are interested in the growth of the running time at astronomically large values of n. At that point, the 2 multiplier in front becomes irrelevant, and that's why it is o(n).

int sum = 0;
for ( int i = 0; i < n; i++)
   for ( int j = i; j < n; j += 2)
      sum++;

In this example, the program will run n*(n/2) times.

n times in the i loop and n/2 times in the j loop

again, since we are interested in the growth of this function at astronomically large values of n, the 1/2 factor for the n becomes irrelevant, making the running time n*n, or n^2

Complexity in terms of Θ

2 Answers2