3 Replies - 127 Views - Last Post: 28 December 2018 - 06:25 PM

#1 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • Posts: 93
  • Joined: 27-December 18

Time Complexity of Algorithmic (DATA STRUCTURE)

Posted 28 December 2018 - 05:14 PM

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?!

Is This A Good Question/Topic? 0
  • +

Replies To: Time Complexity of Algorithmic (DATA STRUCTURE)

#2 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12494
  • View blog
  • Posts: 45,628
  • Joined: 27-December 08

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.
Was This Post Helpful? 0
  • +
  • -

#3 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • Posts: 93
  • Joined: 27-December 18

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!!

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.

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12494
  • View blog
  • Posts: 45,628
  • Joined: 27-December 08

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1