Analyze the following pseudo-code, and answer the questions below. Each question
ID: 3665674 • Letter: A
Question
Analyze the following pseudo-code, and answer the questions below. Each question asks you to analyze the code
under the assumption of a cost for the function doSomething(). For these questions you don’t need to provide a
justification.
i 1
while(i<n)
doSomething(...)
i i * 2
done
1
1. What is the worst case time complexity (Big-O) of this loop if doSomething(...) is an O(1) algorithm?
2. What is the worst case time complexity (Big-O) of this loop if doSomething(...) is an O(n) algorithm?
3. What is the worst case time complexity (Big-O) of this loop if doSomething(...) is an O(m) algorithm? Note:
treat m as an independent size parameter.
4. What is the worst case time complexity (Big-O) of this loop if doSomething(...) is an O(m!) algorithm? Note:
treat m as an independent size parameter.
Explanation / Answer
1. O(n)
2. O(n^2)
3. O(n*m)
4. O(n*m!)