Log problem plus how to solve Big-omega & Big-O ?

[someone_259@hotmail]

Dear vbforum

I'm having trouble doing these question please help, I have try to do it, but I don’t know is right or not. Please any smart people out there, show me the step to do it.

Thank You!

----------------------Question
Q1)Algorithm A uses 50n log n operations, algorithm B uses n^2 operations.
Determine the value of n such that A this better than B for N >= n .
Log(n) is base10 for A.
 
Q2)Suppose we are comparing implementations of insertion sort and merge sort on the same machine.
For inputs of size n, insertion sort runs in 8(n^2), while merge sort runs in 64n lg n steps. 
For which values of n does insertion sort beat merge sort?
 
Q3)What is the smallest value of n such that an algorithm whose running time is 100 n2 runs faster than
an algorithm whose running time is 2n on the same machine?
 
Q4)
2. Prove that f(x) = 10 + 100lg(x-3) is Big-omega
3. Prove that f(x) = 10 + 100lg(x-3) is Big-O
 
----------------------
 
----------------------Answer
I don’t ready know what do it mean by A beat B, I hope I get the arrow right.
Q1) 
A                B
50nlog(n) <= n^2
 
50nlog(n) <= n^2
----------  ----
n             n
 
50log(n) <= n
 
n=1 try it out
50log(1) <= 1
0 <= 1
0<=n<=1
 
 
 
 
Q2)
8n^2 >= 64nlgn
 
8n^2 >= 64nlgn
------  --------
n          n
 
8n >= 64lgn
 
8n >= 64lgn
----   --------
8         8
 
n >= 8lgn
 
n >= lg(n^8)
 
2^n >= n^8
 
Try to guess
 
n = 0
2^0 >= 0^8
1 >= 0 Yes
 
n=1
2^1 >= 1^8
2 >= 1 Yes
 
n=2
2^2 >=2^8
4 >= 256 No
 
I think 0 <= n <= 1
 
 
 
Q3)
100n^2 <= 2^n
 
Don’t know what to do, try to guess
n = 1/10
100(1/10)^2 <= 2^(1/10)
100(1/100)^2 <= 2^(1/10)
1 <= 2^(1/10)
1 <= 1.07
0 <= n <= 1/10
 
Q4) No Idea, can some one please show step for Big-omega & Big-O?
 
----------------------

Please help.

[zaza]

Q1) The idea of this (and the next two questions) is: which gets the algorithm done in the fewest steps. Algorithm A uses 50n log n operations, whereas algorithm B uses n^2 operations. Don't assume n=1, because this is a sigularity for log n and it honestly isn't what your teacher means, although you can put it down to get a bonus mark if he/she thinks you are clever enough. If n = 2, then algorithm A takes 100 log 2 = 30.1 ops, whereas B takes 4 ops. Clearly, then, B takes considerably fewer operations than A to compute the answer. If n = 200 then A takes 10000 log 200 = 23010 operations whereas B takes 200^2 = 40000 operations. The answer therefore lies somewhere in between, and the turning point will be where 50 n log n is equal to n^2.

Hint: Try n=100

Q2) and Q3) : ditto

Go above n=1 and you'll see that there will be another point at which the algorithms / times are equal.

Q4) No idea what you mean by omega and o, you'll have to be more specific if you want any help.

zaza

[someone_259@hotmail]

Q1) The idea of this (and the next two questions) is: which gets the algorithm done in the fewest steps. Algorithm A uses 50n log n operations, whereas algorithm B uses n^2 operations. Don't assume n=1, because this is a sigularity for log n and it honestly isn't what your teacher means, although you can put it down to get a bonus mark if he/she thinks you are clever enough. If n = 2, then algorithm A takes 100 log 2 = 30.1 ops, whereas B takes 4 ops. Clearly, then, B takes considerably fewer operations than A to compute the answer. If n = 200 then A takes 10000 log 200 = 23010 operations whereas B takes 200^2 = 40000 operations. The answer therefore lies somewhere in between, and the turning point will be where 50 n log n is equal to n^2.

Hint: Try n=100

Q2) and Q3) : ditto

Go above n=1 and you'll see that there will be another point at which the algorithms / times are equal.

Q4) No idea what you mean by omega and o, you'll have to be more specific if you want any help.

zaza

Any idea on how to do it?
Q4)
2. Prove that f(x) = 10 + 100lg(x-3) is Big-omega
3. Prove that f(x) = 10 + 100lg(x-3) is Big-O

A                   B
50nlog(n) <= n^2
 
50nlog(n) <= n^2
----------    ----
n                  n
 
50log(n) <= n
 
n = 100
 
50log(100) <= 100
 
50log(10^2) <= 100
 
50(2) <= 100
 
100 <= 100
 
Big O-notation
We write f(n) = O(g(n)) if there exit constants c > 0, n0 > 0 such
That 0 <= f(n) <= cg(n) for all n >= n0.
Example: 2n^2 = O(n^3)                   (c = 1, n0=2 )
2n^2 <= c n^3 
2 <= c n
 
try n = 2
2 <= c(2)
2/2 <= c
1 <= c
 
Big-omega
F(n): there exist constants c > 0, n0 >0 such that 
0 <= cg(n) <= f(n) for all n >= n0
n^(1/2) = Big-omega(lgn)              (c = 1, n0 = 16)
n^(1/2) >= c lgn              
 
n=16
(16)^(1/2) >= lg(16)
4 >= c lg(2^4)
4 >= 4c
4/4 >= c
1 >= c

[zaza]

A B
50nlog(n) <= n^2

50nlog(n) <= n^2
---------- ----
n n

50log(n) <= n

n = 100

50log(100) <= 100

50log(10^2) <= 100

50(2) <= 100

100 <= 100

You seem to be getting the wrong end of the stick with this. The question is, for what values of n does algorithm A take fewer computations than algorithm B?
When n=100, algorithm A takes 5000 log 100 = 10000 steps
algorithm B takes 100^2 = 10000 steps.

So for n = 100, the two algorithms take the same number of computations to complete - they are both as efficient as each other.

If n = 99, then A takes 4950 log 99 = 9879 steps but B takes 99^2 = 9801 steps. Hence B is the better algorithm to use because it takes fewer steps to complete the calculation.

If n = 101, A takes 5050 log 101 = 10122 steps but B takes 101^2 = 10201 steps, so A beats B. So your answer is:

A beats B for n>100. You can prove this graphically as well.