GATE Overflow | Programming | Test 1 | Question: 28

Question

int foo(int n)
{
    if(n > 10000)
        return 1;
    int sum = 0, i;
    for( i = 0; i < n; i++)
    {
        sum += i;
    }
    return sum;
}

The value returned by the above function is

• A. $\Theta\left(n^2\right)$
• B. $\Theta\left(n\right)$
• C. $\Theta\left(1\right)$
• D. $\Omega\left(n^2\right)$

Answer 1

int foo(int n)
{
    if(n > 10000)
        return 1;
    int sum = 0, i;
    for( i = 0; i < n; i++)
    {
        sum += i;
    }
    return sum;
}

for loop will run 10000 times. 
Sum is sum of 1st 9999 natural numbers.
Sum = 9999*10000/2 = 49995000 = Θ(1)

Comments

Since asymptotic complexity is for large values of n, we can ignore the for loop altogether :P

---

@ arjun sir....we can ignore for loop altogether means........

---

means that won't affect the time complexity.

---

Nice question. Got trolled by it :P

---

for loop will run 10000 times only if n is given as 1000. Right?

---

for time complexity $n_{0}$ is required & here $n_{0}$ is 10000,so we should consider any value greater than 10000.

Is it like that ??

Answer 2

Answer : C

WE always take very large value of n to find Time Complexity . so , here we can ignore loop because it will run only for n <= 10000 . so, here for n > 10000 it run only for 1 time for any large value . so , time complexity = Big Theta(1) // which is average case time complexity