for(i=n/2;i<=n;++i)

Question

i read  time taken loop will run is o(n/2)  but if n=8  loop becomes for(i=4;i<=8;++i)   it print 4,5,6,7,8 , so it runs 5 times then how n/2 can be running time please help :

Comments

it will not be exact $\frac{n}{2}$. Here we are interested in finding how it behaves for large values of $n$.

So, its $i $ goes from $\frac{n}{2}$ to $n$, i incremented by $1$ in each step, i.e., $O(\frac{n}{2})$ or $O(n)$

---

brother can you please explain in detail iam weak in programming

---

When we are interested / asked to find time complexity, we are required to find how function behaves for large value of input/data set.

please read some thoery about what does BIg O notaion, Big theta notation mean and then revert back here . One useful link : https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation . Ask if you still don't get.

---

Seems like you're only interested in answer.

Read Asymptotic Notation. Then if still you don't find answer come here then.

Answer 1

Whenever we are asked to find time complexity we need to find approximate answer not exact answer and we will get approximation only for large values.

Answer 2

let us understand in tis way. our ques is for(i=n/2; i<=n; i++)

let n=8 , then i=8/2 =4

now increment i by1, we get,

i=4 which means 4+0

i=5 => 4+1

i=6 => 4+2

i=7 => 4+3

i=8 => 4+4

so for n value; n=4+k

and k=n-4 = O(n-4)= O(n)

as per your ques. put n=8 in above eq. then k=8-4= 4 i.e half of n ( n/2).

likewise take any value of n , the answer will be same i.e n/2.