1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The order of complexity of the Pascal code -- like n * log(n)...

  1. Jan 15, 2017 #1
    1. The problem statement, all variables and given/known data
    The kind of problems i we are currently dealing with in school are like this:
    Complexity.JPG
    Find the order of complexity of the function
    2. Relevant equations
    3. The attempt at a solution

    Im suppose to guess or calculate the complexity of this based on code sample. Its in Pascal and to clarify what is meant here here is an example of the code and its complexity
    Code (Pascal):

    for k:=1 to n do
       while x>0
          k:=k+1
          x:= x DIV 2
     
    The complexity of this code is ##n*logn##. The k-part is repeated n times while the inner while repeats logn times. How to solve these kinds of problems? What would be the best way?
    As i see this, the i<n part is repeated n times, but the s-part confuses me. I can't see ##2^n##
     
  2. jcsd
  3. Jan 15, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It will help if you look at the first 3 runs through of the outer loop manually. What happens to s in each step? How is that linked to the total iterations in the inner loop?
     
  4. Jan 16, 2017 #3
    In the first run s is 1 and it is assigned to k. Then the inner code runs once, increases k by one and assigns it to s. Then the outer again assigns so to k but now the inner runs twice and increases k by 2. In the next run s is 8. Is that the pattern, then it will be 16 and it runs n times since the outer checks for i<n and it is increased by 1 every time?
     
  5. Jan 16, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The values used for s and k double every time, and they will do that n times, right.

    That should lead to the number of steps done in the inner loop.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: The order of complexity of the Pascal code -- like n * log(n)...
  1. Log(n) algorithm (Replies: 5)

Loading...