|
Find the Big O notation for the following:
1. Given: s is the number of students. It can grow without bounds
t is the number of teachers. It is always twenty times less than s
b is the number of books. It can reach 40,000
for x = 50000 to t/100
blah, blah, blah...
for z = -10000 to b*100
yak, yak, yak...
q=-100000
while q< s*100
blab, blab, blab...
q=q*2
Answer: O(n)
2. With the same givens above, find this Big O
q = b*50
while q < t / 20
yuk, yuk, yuk...
for x = 100 to b * 100
for z = 1 to s * 20
yack, yack, yack..
q = q * 3
Answer: O(N log3 N)
3. With the same givens as problem 1, find this Big O
for x = 1 to t - b
for z = s to s + 1000
yack, yack, yack..
w = 10000
while w < t
w = w * 2
for y = 1 to s * t
yuck, yuck, yuck...
Answer: O(n*n)
4. Again, with the same givens..
x = b
while x < s
for z = 1 to b
for y = 100 to t/50
blah, blah, blah...
x = x + 50
Answer: O(n*n)
5. One more time... same givens..
for x = b to s
for y = b*30 to t / 20
for z = 1 to b * b
t = b
while t < s
t = t * 2
Answer: O(n*n log2n )
6. Write an algorithm that has a Big O of Nlog2N. Use at least 2 variables and tell me about the growth of these 2 variables.
7. Write an algorithm that has a Big O of N^2log2N Again, use at least 2 variables and describe them
|
