1. Limited time only! Sign up for a free 30min personal 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!

What t & n in asypmtotic equation

  1. Jan 20, 2017 #1
    Hi,
    1. The problem statement, all variables and given/known data

    In case of asymptotic notations we use the formula:
    t = c * n
    I dont know what is t and what is n? Is n same thing as the size of problem i.e. input data (or the data we have to process). Does t mean running time? why are we not accounting for number of instructions required to execute the program?

    2. Relevant equations

    t = c * n
    3. The attempt at a solution
    t = running time
    c = constant
    n = size of problem (i.e. the input data)

    Some body please guide me.
    Zulfi.
     
  2. jcsd
  3. Jan 20, 2017 #2

    Mark44

    Staff: Mentor

    Your attempt looks reasonable to me. What the equation t = c * n is saying is that running time is proportional to the size of the problem. If you double the size of the problem, you double the running time.

    The number of instructions in the program stays the same, so the formula doesn't need to take that into account.
     
  4. Jan 21, 2017 #3
    Hi,
    I was considering the logical increase of the instruction. Because if we double the data then for instance the sorting loop would be executed double number of times & thus the number of instructions executed to solve the problem would increase due to this. Although their physical number or count would remain be the same.

    Zulfi.
     
  5. Jan 21, 2017 #4

    Mark44

    Staff: Mentor

    The number of instructions is the same in either case. As I said before, if you double the size of the data, it will take twice as long to process the data. Each instruction in your sorting loop will execute twice as many times, but the number of instructions doesn't change.
     
  6. Jan 21, 2017 #5
    Hi,
    <The number of instructions is the same in either case.>
    Sorry if you dont like my comments stated below:
    If i dont use loop, then for each element we increase in the problem, the number of instructions would increase.
    Kindly explain this.
    Zulfi.
     
  7. Jan 22, 2017 #6

    Mark44

    Staff: Mentor

    This doesn't make sense. Presumably you use a loop to process each data element. Thus it takes a set amount of time to process each element, and each element is processed by the same number of lines of code. If you triple the number of elements, you triple the amount of time to process these elements.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted