retagged by
333 views
0 votes
0 votes
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
retagged by

1 Answer

0 votes
0 votes
  • 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

Related questions

0 votes
0 votes
1 answer
1
Ritaban Basu_23 asked Mar 31, 2016
532 views
2n^2 +nlogn =theta(n^2) ,I have done the lower bound..Like finding out the n0 and the constant.. Help me with the upper bound constant and n0
0 votes
0 votes
1 answer
3
Edwees asked Feb 6, 2017
1,895 views
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...