Purchase Solution

Big O - algorithm comparison

Not what you're looking for?

Ask Custom Question

Suppose program A takes (2^n)/1000 units of time and program B takes 1000(n^2) units. For what values of n does program A take less time than program B.

I am really looking for a detailed explanation on this problem - to check my answer.


Purchase this Solution

Solution Summary

This solution helps with a problem about algorithm comparison.

Solution Preview

Ta = 2^n/1000; Tb = 1000*(n^2)

If Ta < Tb,

2^n/1000 < 1000*(n^2)
(2^n)/n^2 < 1,000,000
Take log on both sides,

n*log 2 - 2log n < 6

n < (6 + 2logn)/log ...

Purchase this Solution

Free BrainMass Quizzes
C++ Operators

This quiz tests a student's knowledge about C++ operators.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

C# variables and classes

This quiz contains questions about C# classes and variables.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.