Question trying to physically understand Algorithm run time as proportionIn CLRS, there's a question in the first chapter that says for certain functions r u n t i m e = f ( n ), to calculate the max number of n given the run time. The math works out simply. For example, for f ( n ) = n microseconds, given a 1 second run time there is 1 s e c o n d 10 − 6 s e c o n d s 2 inputs n, which I got from n m i c r o s e c o n d s = 1 s e c o n d and solving for n.My confusion comes from trying to make a proportion for the system like I would for a dimensional analysis problem. I have n m i c r o s e c o n d s n i n p u t s and the other fraction is 1 s e c o n d x i n p u t s . Here when I solve for x I get 10 6 ∗ n . I think my dimensions don't make sense somehow, but in my head, saying 'it takes square root of n microseconds for n inputs' comes out as n m i c r o s e c o n d s n i n p u t s Thank you!!

Question

Question trying to physically understand Algorithm run time as proportionIn CLRS, there&#039;s a question in the first chapter that says for certain functions   r  u  n  t  i  m  e  =  f  (  n  ), to calculate the max number of   n given the run time. The math works out simply. For example, for   f  (  n  )  =      n   microseconds, given a 1 second run time there is                               1                     s          e          c          o          n          d                                      10                          −              6                                           s          e          c          o          n          d          s                      2   inputs   n, which I got from       n       m  i  c  r  o  s  e  c  o  n  d  s  =  1     s  e  c  o  n  d and solving for n.My confusion comes from trying to make a proportion for the system like I would for a dimensional analysis problem. I have                     n                   m      i      c      r      o      s      e      c      o      n      d      s              n             i      n      p      u      t      s       and the other fraction is             1             s      e      c      o      n      d              x             i      n      p      u      t      s      . Here when I solve for   x I get       10    6    ∗      n  . I think my dimensions don&#039;t make sense somehow, but in my head, saying &#039;it takes square root of n microseconds for n inputs&#039; comes out as                     n                   m      i      c      r      o      s      e      c      o      n      d      s              n             i      n      p      u      t      s      Thank you!!

kilinumad · Accepted Answer

Since no one really answered this, this is what I think is some physical intuition behind the situation.It takes       n       m  i  c  r  o  s  e  c  o  n  d  s to solve a given problem, so no matter what it is true that it took                     n                   m      i      c      r      o      s      e      c      o      n      d      s              p      r      o      b      l      e      m             o      f             a      n      y             s      i      z      e             n      . So if the problem took 1 second to solve (for whatever n), the fraction would be             1             s      e      c      o      n      d      s              p      r      o      b      l      e      m             o      f             s      i      z      e             n      . And since we know the first fraction is always true we can set up a proportion                     n                   m      i      c      r      o      s      e      c      o      n      d      s              p      r      o      b      l      e      m             o      f             a      n      y             s      i      z      e             n        =            1             s      e      c      o      n      d      s              p      r      o      b      l      e      m             o      f             s      i      z      e             n      . So now we can solve the proportion for   n

Open question

Answer & Explanation

New Questions in Pre-Algebra