Same chapter3 marksDifficulty: Medium
Why are constants and lower-order terms dropped from a big O expression?
Complexity and Big O Notation
3 marksDifficulty: Medium
What does big O notation measure, and give the complexity of linear search, binary search and bubble sort.
Original Khojo Papers practice question — not from a past board paper.
Answer
Big O notation gives an upper bound on how the running time or space of an algorithm grows with the size of the input, ignoring constants and lower-order terms. Linear search is O(n), binary search is O(log n) and bubble sort is O(n2).
No citable source has been recorded for this record. Treat it as practice material, not as fact.
Explanation
It describes growth rate, not the actual time, which depends on the machine.
Related questions
From the same topic and chapter, at a similar level.
Same chapter3 marksDifficulty: Medium
Give the time complexity of merge sort, insertion sort in the worst case, and accessing an element of an array by its index.
Complexity and Big O Notation
Same chapter3 marksDifficulty: Medium
State the time complexity of the following and justify it: for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum++;
Complexity and Big O Notation
Same subject3 marksDifficulty: Medium
Write a recursive Java method to compute the factorial of a non-negative integer n.
Recursion
Same subject3 marksDifficulty: Medium
State and verify the absorption law X + X·Y = X using a truth table.
Boolean Algebra
Same subject3 marksDifficulty: Medium
Convert the Boolean expression F(A, B, C) = Σ(1, 3, 5) into its canonical sum of products form.
Boolean Algebra