tweety's blog

Question about time complexity
By tweety, history, 9 years ago, In English

If I had in my algorithm something like this:

for (int i = 0; i < n; i++) if (i % 2) continue; else { code code code... }

Will the time complexity be O(n) or O(n / 2)?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Strictly there are n/2 operations, but in asymptotic notation O(n) = O(n/2), so they are essentially the same (In Big O notation), because n/2 = (1/2)*n and 1/2 is a constant that is not dependent on n.

A more formal definition is to come back to the Big O definition, it means that we can find a constant k such that k*n >= n/2 for sufficiently large n. In simple words it means that n is an upper bound of n/2.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The O(n/2) is only an example. I mean, if I had something like:

    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (j != 0) continue; else { code code code... }

    And the expected time complexity was O(n), would this pass the test cases?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it -8 Vote: I do not like it

      Edit: I didn't see the nested for!

      Yes, that code would get TLE, because at best is O(n^2), that is if we suppose that "code..code" is O(1), if that isn't constant the complexity can be even bigger.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        What are you talking about? Ofcourse answer is No! Complexity of this cycle is O(n2) even if code code code runs in O(1).

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Interesting... VS optimizes this

          #include<iostream>
using namespace std;
int main()
{
	long long cnt = 0;
	for (long long i = 1; i <= 1000000; i++)
	{
		for (long long j = 1; j <= 1000000; j++)
		{
			if (j == 0)
			{
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

          but not this

          #include<iostream>
using namespace std;
int main()
{
	long long cnt = 0;
	for (long long i = 1; i <= 1000000; i++)
	{
		for (long long j = 1; j <= 1000000; j++)
		{
			if (i == 0)
			{
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}
          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Wouldn't pass because it will perform O(N2) operations. If you replace the continue with break then your complexity will be O(N) and it would pass. This is all assuming "code code code" runs in O(1)

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Strictly there are n operations as if is operation too. If example is simple, like here, compiler may optimize it to run faster but it is not guarenteed.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I checked this

      int main()
{
	int cnt = 0;
	for (int i = 1; i <= 10000000; i++)
	{
		if (i % 2 == 0)
		{
			cnt++;
		}
	}
}

      code is disassembler. VS 2013 doesn't optimize it neither in debug nor in realise mode :(

      → Reply