Hi guys, I'm just wondering of how I can decide if the algorithm is o(n) linear of growth or not linear?

for example if I have input of size n, and if in every iteration I subtract 1 then we say the algorithm is growing linear as O(n) but why?! what's confusing me how are we determining that the algorithm is growing linear or not? by which pattern we decide the algorithm is linear?!

for example if I have in every iteration respectively like this n-1, n-2, n-3, n-4,n-4,n-5, ....etc then we say that the algorithm is gowring linear O(n) why?!

And why when we have n-c then we say its linear growing?!

# Time Complexity of Algorithmic (DATA STRUCTURE)

Page 1 of 1## 3 Replies - 127 Views - Last Post: 28 December 2018 - 06:25 PM

##
**Replies To:** Time Complexity of Algorithmic (DATA STRUCTURE)

### #2

## Re: Time Complexity of Algorithmic (DATA STRUCTURE)

Posted 28 December 2018 - 05:28 PM

I'm not sure I understand your question. Does the loop require n iterations, where each iteration takes a constant number of steps? Or on iteration i of n, does the loop require n-i steps?

In the first case, we note that the runtime function of the algorithm is T(n) = cn, where c is the number of steps required in each iteration. So T(n) = O(n).

In the second case, we have that T(n) = (n-1) + (n-2) + (n-3) + ... + 0 = \sum_{i=1}^{n} (n-i) = \sum_{i=1}^{n} n - \sum_{i=1}^{n} i = n^2 - n(n+1)/2 = n(n-1)/2 = O(n^2).

Also, not to be rude, but you are rambling in your OP. It is very hard to follow your thought process. Please try to be clearer and more precise, so that we can better help you.

In the first case, we note that the runtime function of the algorithm is T(n) = cn, where c is the number of steps required in each iteration. So T(n) = O(n).

In the second case, we have that T(n) = (n-1) + (n-2) + (n-3) + ... + 0 = \sum_{i=1}^{n} (n-i) = \sum_{i=1}^{n} n - \sum_{i=1}^{n} i = n^2 - n(n+1)/2 = n(n-1)/2 = O(n^2).

Also, not to be rude, but you are rambling in your OP. It is very hard to follow your thought process. Please try to be clearer and more precise, so that we can better help you.

### #3

## Re: Time Complexity of Algorithmic (DATA STRUCTURE)

Posted 28 December 2018 - 05:51 PM

Sorry about that next time i will clear it; what im asking is why when we add constany or subtract constant from n then we say that the growing is linear? How we are determining that the growing is linear or not? for example n-10 we say thats linear growing..why?

Thanks alot!!

Thanks alot!!

This post has been edited by **Skydiver**: 29 December 2018 - 05:38 PM

Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

### #4

## Re: Time Complexity of Algorithmic (DATA STRUCTURE)

Posted 28 December 2018 - 06:25 PM

For the runtime function T(n), we say that T(n) = O(n) if there exist positive constants c and k such that T(n) <= cn for n >= k.

Suppose T(n) = n-10. Take c = k = 1. Then we have that n-10 <= n for all n >= k.

Suppose T(n) = n-10. Take c = k = 1. Then we have that n-10 <= n for all n >= k.

Page 1 of 1