Prof said these should be pretty short and simple...I have an idea but just want

Question

Prof said these should be pretty short and simple...I have an idea but just want to verify...

1) Solving a problem requires running an O(N) algorithm and then afterwards a second O(N) algorithm. What is the total cost of solving the problem.

2) Solving a problem requires running an O(N^2) algorithm and then afterwards a second O(N) algorithm. What is the total cost of solving the problem.

3) Solving a problem requires running an O(N) algorithms and then afterwards N binary searchers, then running another O(N) algorithm. What is the total cost of solving the problem.

Explanation / Answer

You can treat these problems like math problems and combine like terms and/or simplifying the problem. The main approach with Big-O notation is that you only care about the highest order term (O(n^2) is higher than O(n) so if the running time is (n^2)+(n)+c (some constant)) then the program runs in O(n^2) because that's the high order term so you drop everything else. 1. O(n)+O(n)=2*O(n) (but in big O notation you would consider this O(n) because the function is basically determined by n occurrences). 2. O(n^2)+O(n)=O(n^2) (again you drop the low ordered term (O(n))) 3. Here you need to know that one Binary search runs in O(log n) which means 2 to some power = n so a binary search where n=16 is 4 steps (2^4) (For computer science Logs are always base 2). The equation should be O(n)+O(n log n) + O(n) = O(n log n) + O(2n) so since n log n (for a sufficiently large n) is greater than 2n the running time is O(n log n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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