8 Questions
What is the time complexity of the given code snippet: int vectorMax(Vector &v) { ... }
O(n)
What is the time complexity of the function int nestedLoop1(int n) { ... }
O(n^2)
What is the time complexity of the function int nestedLoop2(int n) { ... }
O(n^3)
What is the time complexity of the function int binarySearch(int* list, int size, int target) { ... }
O(log n)
What is the Big O notation for the expression 34𝑛³ + 17𝑛 log 𝑛 + 19
O(n^3)
Which of the following is an example of exponential time complexity?
O(2^n)
What is the main approach to simplifying Big O notation expressions?
Strip the constants and take the largest term
Why do we ignore primitive operations when analyzing time complexity?
Because they have a negligible impact on the overall time complexity
Study Notes
Big O Notation Revision
Complexity Notations
- O(1) represents constant complexity
- O(log n) represents logarithmic complexity
- O(n) represents linear complexity
- O(n2) represents quadratic complexity
- O(2n) represents exponential complexity
- O(nk) (k>=1) represents polynomial complexity, except O(n2)
Evaluating Big O Notation
- To evaluate the Big O notation of an expression, strip the constants and find the biggest factor
- Example: 34𝑛3 + 17𝑛 log 𝑛 + 19 => O (𝑛3)
- Another example: 𝑛3 + 𝑛 log 𝑛 => O (𝑛3)
Code Analysis
VectorMax Function
- The function has a linear complexity of O(n) because it iterates through the vector once, ignoring primitive operations and taking the worst-case behavior
Nested Loop Functions
- The first nested loop function has a quadratic complexity of O(n2) due to the two nested loops
- The second nested loop function has a polynomial complexity of O(n3) due to the three nested loops
Binary Search
- The binary search function has a logarithmic complexity of O(log n) because it uses a divide-and-conquer approach
Review and practice Big O notation concepts, including complexity notations and evaluating expressions.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
