Big O

Question

The concept of order (Big O) is important because—
(a) it can be used to decide the best algorithm that solves a given problem
(b) it determines the maximum size of a problem that can be solved in a given system, in a given amount of time
(c) it is the lower bound of the growth rate of the algorithm
(d) Both (a) and (b)

Answer 1

let problem A of size is n.
Big O says time taken by best algorithm that solve every case(best, avarage, worst) of problem A completely.
in general Big O is "The Best algorithm of worst case input".
it also determines the max size of problem that can be solved in given amount of time.

Comments

Hi

This is an informal explanation that i could provide you  

Let me add some things to above answer .We know that Big Oh notation is used in time complexity . the reason why we called Big Oh because it say "at any condition this is worst time that an algorithm could take "

where as Big Omega says its is "best time that you can get , You cant getter better than this . For example in A linear search if you want to find out element and the required element is at first position . then this would be best thing , you cant get anything better than this "

Where as Theta notation is an combination of big oh and big omega . In general you can say An average case

So from all above if you see , the Big Oh notaion would be able to give best idea (Worst, average , Best) Hence option a

Option b is stupid option ( you dont have anything to do with maximum no of input )

And Option c is wrong because Big Oh give the highest bound "(maximum time that your algorithm would take in any case ")

---

why option "b" is stupid?

---

oops sorry i didint read statement properly

Big oh is actually a relationship between Input and time

. It shows us the time taken as size of input increases !

So then "d" become tha answer (both a and b)

Answer 2

big O  is the time taken by an algorithm which is the worst case scenario i.e  " the input arrangement for which the algo. does maximum work and takes maximum time "

suppose for quick sort , in  worst case  it takes O(n^2)

it means that for sorting n number (which may or may not be in order) maximum time it will take is O(n*n).

Answer 3

Only option D is correct.

Option A is valid because big O will tell the maximum number of comparisons in the algorithm. Even the best algorithm will have the worst case time, hence big O can be taken as a deciding factor in the worst scenario.