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

[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