in Programming
886 views
7 votes
7 votes
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

  1. $\Theta\left(n^2\right)$
  2. $\Theta\left(n\right)$
  3. $\Theta\left(1\right)$
  4. $\Omega\left(n^2\right)$
in Programming
by
886 views

2 Answers

10 votes
10 votes
Best answer
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)
selected by

4 Comments

Nice question. Got trolled by it :P
4
4
for loop will run 10000 times only if n is given as 1000. Right?
0
0
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 ??
0
0
0 votes
0 votes

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

Answer:

Related questions