• Support PF! Buy your school textbooks, materials and every day products Here!

I need help with some algorithms problems

  • #1
I'm having problems solving this assignment. I don't understand how to solve for big-oh, big omega or big theta.

0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)).

f(n)---------------------g(n)
(a) n - 100------------ n - 200
(b) n^1/2 --------------n^2/3
(c) 100n + log n--------n + (log n)2
(d) n log n-------------10n log 10n
(e) log 2n-------------- log 3n
(f) 10 log n------------- log(n2)
(g) n^1.01-------------- n log^2 n
(h) n^2/log n-----------n(log n)^2
(i) n^0.1----------------(log n)^10
(j) (log n)^log n--------- n/log n
(k) sq root of n----------(log n)^3
(l) n^1/2 ---------------5^log2 n
(m) n2^n-------------------3^n
(n) 2^n------------------ 2^n+1
(o) n!----------------------2^n
(p) (log n)^log n------- 2^(log2 n)^2


0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c2 + . . . + c^n is:
(a) Θ(1) if c < 1.
(b) Θ(n) if c = 1.
(c) Θ(c^n) if c > 1.



The dashes in the first problem are only meant to separate the two columns for visibility.
What I know is this. f = O(g) means f <= g. f = Ω(g) means g = O(f). f = Θ(g) means f = O(g) and f = Ω(g). I'm a little confused right now, I'd appreciate some help.
 
Last edited:

Answers and Replies

Related Threads for: I need help with some algorithms problems

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
912
Replies
2
Views
884
Replies
0
Views
3K
Replies
55
Views
4K
Replies
25
Views
2K
Top