time complexity

Question

What is the time complexity of fun()?

int fun(int n)
{
  int count = 0;
   for (int i = 0; i < n; i++)
   for (int j = i; j > 0; j--)
   count = count + 1;
  return count;
} 

 

Comments

Are you sure the question is correct?

This seems like a typo - where did j come from?

Assuming the inner loop is (int j = i; j > 0; j--).

When i = 0, it executes 0 times.
When i = 1, it executes 1 time.
When i = 2, it executes 2 time.
When i = 3, it executes 3 times and so on till when i = n-1, j will also be executed n -1 times.

The number of basic operations performed will be $1 + 2 + 3 +  \dots + n -1$ which is known to be $O(n^2)$.

I am not sure about this though, so if someone could check this that'd be great.
​​​​​​​

---

goxul I THINK U R RIGHT .

BUT THEY ASK COUNT NOT TIME COMPLEXITY .

SO COUNT =n^2-n/2

---

https://www.geeksforgeeks.org/algorithms-gq/analysis-of-algorithms-gq/

go through this link and q..no 6

Answer 1

Here count is just a return value  and the complexity depends on two loops mostly on  the loop

there due to j=1 and  j>0 for the first time the loop will executed only 0 times

i =0                  i=1                                            i=2

j=0 times         j will be executed 1 time         j  will be executed 2 times

summing all the  executions of j we will get O(n Square)

Answer 2

For these questions we will try to find out number of times “count = count + 1;” gets executed.

 

i	0	1	2	3	………...	(n-1)
value of j	0	1	2 values(2,1)	3 values (3,2,1)	………...	(n-1) values (n-1,n-2,….,1)

 value of j indicates the number of times “count = count + 1;” gets executed for each value of i.

So, 0+1+2+3+…...(n-1) times

= $\frac{(n-1)*n}{2}$

=$\frac{(n^{2}-n)}{2}$

 So, time complexity is $O(n^{2})$

And since each execution of j for loop increments count by 1 so value of count = $\frac{(n^{2}-n)}{2}$