60 views
I have read in some books in design and analysis of algorithms that:

in big-oh(O),omega and  theta notations we need to have constants c,n,n0;

what are these constants ,what is there use and can please any one explain me what is the significance of each term .

i think :

n=value of the input;

n0=no.of inputs;

Am i right in this ,or wrong
| 60 views
0
which book? i haven't heard that
0
ok i was confused with term "constants" you mean notations( n,c,n0)
0
Yes,what are those notations
0

• N means the order of input. If I were to find the big Oh (casually read time it takes for completing a task) for particular algorithm, then if I say it is order of N log N, it means if there are N items in input, this would be the behavior of the algorithm, which means with increasing value of N
• C is a constant which is sometimes used to get the absolute value for a particular machine. If I say it takes 100 secs to sort 1000 numbers on machine X using quick sort, then how much will it take to sort 10000 numbers using quick sort on same machine. Then you can find value of C using
N log N + c = 100 secs
==> 1000 log 1000 + c = 100 secs
==> c = whatever

• I have never heard of n0
by Loyal (5.5k points)