Htykuut

I am trying to rank these functions — 2n, n¹⁰⁰, (n + 1)², n·lg(n), 100n, n!, lg(n), and n⁹⁹ + n⁹⁸ — so that each function is the big-O of the next function, but I do not know a method of determining if one function is the big-O of another. I'd really appreciate if someone could explain how I would go about doing this.

Assuming you have some programming background. Say you have below code:

void SomeMethod(int x)

{       

    for(int i = 0; i< x; i++)

    {

            // Do Some Work

    }

}

Notice that the loop runs for x iterations. Generalizing, we say that you will get the solution after N iterations (where N will be the value of x ex: number of items in array/input etc).
so This type of implementation/algorithm is said to have Time Complexity of Order of N written as O(n)

Similarly, a Nested For (2 Loops) is O(n-squared) => O(n^2)

If you have Binary decisions made and you reduce possibilities into halves and pick only one half for solution. Then complexity is O(log n)

Found this link to be interesting.

For: Himanshu

While the Link explains how log(base2)N complexity comes into picture very well, Lets me put the same in my words.

Suppose you have a Pre-Sorted List like:

1,2,3,4,5,6,7,8,9,10

Now, you have been asked to Find whether 10 exists in the list. The first solution that comes to mind is Loop through the list and Find it. Which means O(n). Can it be made better?

Approach 1:

As we know that List of already sorted in ascending order So:

• Break list at center (say at 5).


• Compare the value of Center (5) with the Search Value (10).


• If Center Value == Search Value => Item Found


• If Center < Search Value => Do above steps for Right Half of the List


• If Center > Search Value => Do above steps for Left Half of the List

For this simple example we will find 10 after doing 3 or 4 breaks (at: 5 then 8 then 9) (depending on how you implement)

That means For N = 10 Items - Search time was 3 (or 4). Putting some mathematics over here;

2^3 + 2 = 10 for simplicity sake lets say

2^3 = 10 (nearly equals --- this is just to do simple Logarithms base 2)

This can be re-written as:

Log-Base-2 10 = 3 (again nearly)

We know 10 was number of items & 3 was the number of breaks/lookup we had to do to find item. It Becomes

log N = K

That is the Complexity of the alogorithm above. O(log N)

Generally when a loop is nested we multiply the values as O(outerloop max value * innerloop max value) n so on. egfor (i to n){ for(j to k){}} here meaning if youll say for i=1 j=1 to k i.e. 1 * k next i=2,j=1 to k so i.e. the O(max(i)*max(j)) implies O(n*k).. Further, if you want to find order you need to recall basic operations with logarithmic usage like O(n+n(addition)) <O(n*n(multiplication)) for log it minimizes the value in it saying O(log n) <O(n) <O(n+n(addition)) <O(n*n(multiplication)) and so on. By this way you can acheive with other functions as well.

Approach should be better first generalised the equation for calculating time complexity. liken! =n*(n-1)*(n-2)*..n-(n-1)so somewhere O(nk) would be generalised formated worst case complexity like this way you can compare if k=2 then O(nk) =O(n*n)