(a1,...,an)(b1,...,bm)
 x <- 0
 i <- 1
 while i < n and ai > 0 do
     for j <- i to m do
         x <- x + ai x bj
     i <- i + 1
 return x

So with this algorithm I've been tasked with finding the run time, though it has 2 loops in it. Considering it has 2 for loops that would lead to it being just n x n = O(n²) right? Though the 2 comparison operators in the while loop are confusing me I don't think it's as straightforward as I think it is.

  • The only variable within the loops that participates in the loop conditions is i, and it's a simple increment. – Robert Harvey Nov 7 at 18:09
  • 3
    Possible duplicate of What is O(...) and how do I calculate it? – Robert Harvey Nov 7 at 18:10
  • So the comparisons do not increase run time especially? And increments are done in constant time right? – bemzoo Nov 7 at 18:14
  • 1
    So the comparisons do not increase run time especially? -- It doesn't matter. You're not assessing run time with Big O; you're assessing scalability. (the ability for the function to scale as n becomes large). – Robert Harvey Nov 7 at 18:24
  • And increments are done in constant time right? -- Yes. – Robert Harvey Nov 7 at 18:24

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.