What t & n in asypmtotic equation

  • Thread starter zak100
  • Start date
  • #1
462
11
Hi,
1. Homework Statement

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?

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.
 

Answers and Replies

  • #2
34,020
5,673
Hi,
1. Homework Statement

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?

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.
 
  • #3
462
11
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.
 
  • #4
34,020
5,673
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.
 
  • #5
462
11
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.
 
  • #6
34,020
5,673
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.
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.
 

Related Threads on What t & n in asypmtotic equation

Replies
3
Views
2K
Replies
6
Views
1K
  • Last Post
Replies
3
Views
4K
Replies
5
Views
1K
  • Last Post
Replies
13
Views
2K
Replies
7
Views
648
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
838
Replies
4
Views
9K
Replies
11
Views
913
Top