Блог пользователя tweety

Question about time complexity
Автор tweety, история, 9 лет назад, По-английски

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)?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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).

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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;
}
          → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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)

      → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

    → Ответить