What t & n in asypmtotic equation

[zak100]

Hi,
1. Homework Statement
In case of asymptotic notations we use the formula:
t = c * n
I don't 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?

Homework Equations

t = c * n

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.

 

[Mark44]

Hi,
1. Homework Statement
In case of asymptotic notations we use the formula:
t = c * n
I don't 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?

Homework Equations

t = c * n

The Attempt at a Solution

t = running time
c = constant
n = size of problem (i.e. the input data)

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.

 

[zak100]

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.

 

[Mark44]

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.

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.

 

[zak100]

Hi,
<The number of instructions is the same in either case.>
Sorry if you don't like my comments stated below:
If i don't use loop, then for each element we increase in the problem, the number of instructions would increase.
Kindly explain this.
Zulfi.

 

[Mark44]

Hi,
<The number of instructions is the same in either case.>
Sorry if you don't like my comments stated below:
If i don't use loop, then for each element we increase in the problem, the number of instructions would increase.

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.