ELEVATE SKILLS!
Enquiry FormRSSBRPSCUniversity of RajasthanRTU KotaCareers@SA
ELEVATE SKILLS!

CS Free MCQ Bank

Access a comprehensive computer science MCQ bank for free, featuring hundreds of questions with detailed solutions. Strengthen concepts, practice effectively, and prepare confidently for exams, quizzes, and competitive tests.

  • Home
  • CS MCQs
  • DSA
  • Suraku Academy | DSA - Time - Space Complexity Solved MCQs & PYQs

Q: 1 What is the time complexity of an infix to postfix conversion algorithm?

  1. O(N log N)

  2. O(N)

  3. O(N2)

  4. None of the above

[ Option B ]

The time complexity of converting an infix expression to a postfix expression is O(N). This is because the algorithm scans the infix expression one character at a time from left to right.
For each character (operands, operators, parentheses), the algorithm may push it onto a stack or pop it from the stack. Each element is pushed and popped at most once, so the total number of operations grows directly with the length of the expression.
Since no nested loops or repeated scans are used, the overall work done is proportional to N, where N is the number of characters in the expression. Therefore, the time complexity is O(N).

ALGORITHMTIME COMPLEXITY
Infix to Postfix Conversion.O(N)
Infix to Prefix Conversion.O(N)
Postfix Expression Evaluation.O(N)
Prefix Expression Evaluation.O(N)
Balanced Parentheses Checking.O(N)
String Reversal Using Stack.O(N)

Q: 2 Which of the following options correctly matches the asymptotic notation.

  1. Big-O Notation (O-notation) : Average Case complexity
    Omega Notation (Ω-notation) : Worst Case complexity
    Theta Notation (Θ-notation) : Best Case complexity

  2. Big-O Notation (O-notation) : Best Case complexity
    Omega Notation (Ω-notation) : Average Case complexity
    Theta Notation (Θ-notation) : Worst Case complexity

  3. Big-O Notation (O-notation) : Worst Case complexity
    Omega Notation (Ω-notation) : Average Case complexity
    Theta Notation (Θ-notation) : Best Case complexity

  4. Big-O Notation (O-notation) : Worst Case complexity
    Omega Notation (Ω-notation) : Best Case complexity
    Theta Notation (Θ-notation) : Average Case complexity

[ Option D ]

Asymptotic Notation is used to measure how the running time of an algorithm grows as the input size increases. It does not count exact time, but shows the behavior of the algorithm for large inputs.
Big-O Notation (O):
Big-O tells us the worst-case performance of an algorithm. It means the maximum time an algorithm may take in the worst situation. Big-O answers the question: “What is the slowest this algorithm can be?”
Omega Notation (Ω):
Omega represents the best-case performance of an algorithm. It shows the minimum time required when the input is in the most favorable condition. Omega answers the question: “What is the fastest this algorithm can be?”
Theta Notation (Θ):
Theta gives the average or exact growth rate of an algorithm. It is used when the best case and worst case grow at the same rate. Theta answers the question : “On average, how does this algorithm perform?”
E.g.: 
If searching for an element in a list:

  • Best case (Ω): Element found at first position.
  • Worst case (O): Element found at last position or not found.
  • Average case (Θ): Element found somewhere in the middle.

In short:

  • Big-O : Worst Case / Upper Bound.
  • Omega (Ω) : Best Case / Lower Bound.
  • Theta (Θ) : Average Case / Tight Bound.

Q: 3 For defining the best time complexity, let f(n) = log(n) and g(n) = √n, ……..

  1. f(n) ∈ Ω(g(n)), but g(n) ∉ Ω(f(n))

  2. f(n) ∉ Ω(g(n)), but g(n) ∈ Ω(f(n))

  3. f(n) ∉ Ω(g(n)), and g(n) ∉ Ω(f(n))

  4. f(n) ∈ Ω(g(n)), and g(n) ∈ Ω(f(n))

[ Option B ]

Q: 4 What would be the time complexity of a code that contains n nested loops running from 1 to m.

  1. O(n+m)

  2. O(n*m)

  3. O(nm)

  4. O(mn)

[ Option D ]

When a code contains n nested loops, and each loop runs from 1 to m, the inner loop executes m times for every iteration of the outer loop.
For two nested loops running from 1 to m time complexity will be m2 . Similarly, for n nested loops running from 1 to m time complexity will be mn.

  • O(n+m) applies to sequential loops.
  • O(n*m) applies when there are two loops where one depends on n and the other on m.
LOOP SCENARIODESCRIPTIONTIME COMPLEXITY
Loop with constant work.Loop runs fixed number of times.O(1)
Single loop.One loop running from 1 to n.O(n)
Two sequential loops.One loop after another, both 1 to n.O(n+n) ≈ O(n)
Two nested loops.Outer loop 1 to n, inner loop 1 to n.O(n2)
Three nested loops.Three loops each 1 to n.O(n3)
The k nested loops.The k loops each 1 to n.O(nk)
Two nested loops with different limits.Outer 1 to n, inner 1 to m.O(n*m)
The n nested loops, each 1 to m.The n loops all running 1 to m.O(mn)

Thank You for Reading!

Thank you so much for taking the time to read my Computer Science MCQs section carefully. Your support and interest mean a lot, and I truly appreciate you being part of this journey. Stay connected for more insights and updates! If you'd like to explore more tutorials and insights, check out my YouTube channel.

Don’t forget to subscribe and stay connected for future updates.