Standard form means simplify in this case. Here are two problems on understandin

Question

Standard form means simplify in this case.

Here are two problems on understanding the growth rate oC functions that represent running times of algorithms and the use of asymptotic notation. Take the following list of functions (from nonnegative integers to nonnegative integers') and arrange them in ascending order of growth. Thus, if a function g immediately follows f in the list, then f= 0(g) Some of these functions are described in words and some as summations. For every function described in words or is a summation, write it in standard form first before placing it in the sorted Viet of functions Show your work in order to receive partial credit. 26 1og n The running time of the binary Search algorithm 100n2 + 1000000 2n (log2 n)2 middot n i=1 theta ( 1) n3/(log2n )4 2 log2 100

Explanation / Answer

Asymptotic Notations :

We have discussed Asymptotic Analysis, and Worst, Average and Best Cases of Algorithms. The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs to be compared. Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis

Notation:

            The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.
A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants. For example, consider the following expression.
                              3n3 + 6n2 + 6000 = (n3)
Dropping lower order terms is always fine because there will always be a n0 after which (n3) beats n2)

Big O Notation:

                    The Big O notation defines an upper bound of an algorithm, it bounds a function only from above. For example, consider the case of Insertion Sort. It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2). Note that O(n^2) also covers linear time.
If we use notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:
1. The worst case time complexity of Insertion Sort is (n^2).
2. The best case time complexity of Insertion Sort is (n).

Notation:

             Just as Big O notation provides an asymptotic upper bound on a function, notation provides an asymptotic lower bound.

Notation< can be useful when we have lower bound on time complexity of an algorithm. As discussed in the previous post, the best case performance of an algorithm is generally not useful, the Omega notation is the least used notation among all three.

Running time of binary search :

    In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array.The binary search algorithm can be classified as a dichotomic divide-and-conquer search algorithm and executes in logarithmic time.

Worst case is when item X is not found.
How many iterations are executed before Low > High?
Low = 0; High = N - 1;

while( Low <= High )          
{
Mid = ( Low + High ) / 2; // Find middle index
if( X > A[ Mid ] ) // Search second half of array
Low = Mid + 1;
else if( X < A[ Mid ] )     // Search first half
High = Mid - 1;
else return Mid;             // Found X!
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.