Find the domain terms and specify the Big-Oh complexity of the algorithm.
QUESTION
Following are various algorithms’ time complexities expressions, find the dominant terms and specify the big-oh complexity of each algorithm.
| S.NO | Expression | Dominant term | O |
| 1 | 75 + 0.001n1.3 + 0.025n+(1000)4 | ||
| 2 | 500n+100n+50n logn | ||
| 3 | (10n1.5)4+0.3n+5 n6.5+2.5 n2.75 | ||
| 4 | 150n3+n2log2n+n(log2n)4 | ||
| 5 | 3log10n+log2log2n | ||
| 6 | 100n4+0.01n2+200(log2n)4 | ||
| 7 | n3+0.01n+100n2+5n3 | ||
| 8 | 2n0.5+n0.35+0.5n0.25 | ||
| 9 | 0.01n2log2n+n5log3n+100n4 | ||
| 10 | 50n3log3n+n5log3n+100n4 |
SUMMARY
The two questions are related to asymptotic notations and stacks.
ANSWER:
Big-Oh notation represents the time complexity of algorithms in terms of order of growth. The upper bound for a function is represented by Big-Oh.
The order of growth is given by,
c< log log n< log n< n1/3< n1/2< n< n2< n3< n4< 2n< nn
To find out the dominant terms, we need to follow two steps
a) ignore coefficient terms
b) get the highest term in terms of order of growth
using these we get,
| S.NO | Expression | Dominant term | O |
| 1 | 75 + 0.001n1.3 + 0.025n+(1000)4 | 0.01n1.3 | O(n1.3) |
| 2 | 500n+100n+50n logn | 50nlog10n | O(nlog10n) |
| 3 | (10n1.5)4+0.3n+5 n6.5+2.5 n2.75 | 5n6.5 | O(n6.5) |
| 4 | 150n3+n2log2n+n(log2n)4 | 150n3 | O(n3) |
| 5 | 3log10n+log2log2n | 3log10n | O(log10n) |
| 6 | 100n4+0.01n2+200(log2n)4 | 100n4 | O(n4) |
| 7 | n3+0.01n+100n2+5n3 | 6n3 | O(n3) |
| 8 | 2n0.5+n0.35+0.5n0.25 | n0.35 | O(n0.35) |
| 9 | 0.01n2log2n+n5log3n+100n4 | 0.01n2log2n | O(n2log2n) |
| 10 | 50n3log3n+n5log3n+100n4 | n5log3n | O(n5log3n) |
![]()
QUESTION
Consider an empty stack stk of size 5(array-based implementation). What will be the output after applying the following stack operations? Draw a diagram in support of your answer. How many elements are there in the stack at the end of the processing?
POP(),PUSH(9),PUSH(11),PUSH(25),POP(),POP(),PUSH(42),POP(),PUSH(3),PUSH(7),PUSH(13),PUSH(15).PUSH(54),POP(),PUSH(50)
ANSWER
Stack is basically a linear data structure. It follows a LIFO structure which means Last In First Out. This means that insertion and deletion operations are done on the same end.
PUSH() is used for insertion and POP() is used for deletion.
If the stack is empty and the pop operation is performed, there will be no change in the size of the stack. Similarly, if the stack is full and elements are pushed into it, they will not be added to the stack and therefore it remains the same.
The size of the stack after performing the operations is 5.
Also read: Implement a bag class using a linked list