Q 1
The order is:
f6(n) f3(n) f5(n) f2(n) f1(n) f4(n)
Because f6(n) is Θ (n1/2), f3(n) is Θ (nlog(n)),
f5(n) is Θ (n5), f2(n) is Θ (n8), f1(n) is Θ (2n log n)
and f4(n) is Θ (6n ).
Q2
(a) Running Time: Θ(n)
· The first and second loop both iterate about n/2 times
· So the best and worst running time both are Θ(n).
(b) Running Time: Θ(n)
It iterates n times. In every iteration, it does a test and possibly
a assignment. But it is still Θ(1) in every iteration.
So the best and worst running time both are Θ(n).
(c) Running Time: Θ((mn)1/2)
Outer loop iterates n1/2, inner loop is m1/2, so best and worst running time both are Θ((mn)1/2).
(d) Running Time: Θ(n2m)
The outer loop iterates n times, the middle loop iterates
O(n) times, the inner loop iterates m times. So best and worst running time both are Θ(n2m).
(e) Best running time is Θ(n).
Worst running time is Θ(nmp).
The for loop iterates n times.
In the best case, when b1==0, the outer while loop will run
O(1), so the best running time is Θ(n).
In the worst case, when no element of b is 0 and no element
of c is 0, the outer while loop will iterate m times and the inner while loop will iterate p times. So the worst running time is Θ(nmp).
Q 3
(a) True.
Because the asymptotic running time of Algorithm A is Θ(n4), means A’s asymptotic upper bound and asymptotic lower bound are both n4 , so A is Ω(n4).
(b) False.
Because every function that is in Θ(n4) will not be in Θ(n3).(c
(c) True.
Because function in Θ(n6)
is in O(n6) and also in Ω(n)
and
Ω(n3) which is consistent with the statements.
(d) False.
From statement 4, the running time of Algorithm B must be in Ω(n3), that is its lower bound is n3 so it can’t have upper
bound n2 .
(e) True.
Because function in Θ(n6)
is in O(n6) and also in Ω(n)
and
Ω(n3) which is consistent with the statements.
Q4
(a)
Sort the tokens in D by length, from longest to shortest.
For each token t in D:
valid = true
For each w in L:
If substring(t, w) == false:
valid = false
break
if valid:
return t
return “”
(b)
Sort the sequence D will take O(nlog(n)). Because length(w) takes O(1) and we can use algorithm such as merge sort to sort
the sequence in O(nlog(n)).
We could use Knuth-Morris-Pratt algorithm to implement the substring function. This algorithm takes Θ(len(w)) to pre-compute the pattern from string w and takes Θ(len(w’)) to do the find the string w in w’. So in the pseudo code above, to find if a token t is a substring of all the words in D, we will take O(len(t) + len(w1) + len(w2) + … len(wm)).
In the the best-case scenario when the longest token tl is a substring of all the words in L. Suppose len(w1) + len(w2) + … len(wm) = total_len_L, from above analysis, it will take
Θ (len(tl) + total_len_L) to confirm it is a substring of all words in L. So the overall time is Θ(nlog(n) + len(tl) + total_len_L).
In the worst case scenario when all the tokens are a substring of
the words w1…wm-1 but not wm. Suppose len(t1) + len(t2) + … len(tn) = total_len_D. Then the total time to do the substring matching is Θ(total_len_D + total_len_L), plus the sorting time, the worst case running time is
Θ(nlog(n) + total_len_D + total_len_L).
/docProps/thumbnail.jpeg