Interview Preparation Time Complexity | Quiz Part 01 Question with Answers

Are you preparing for an upcoming job interview but aren’t sure what to expect? Here are the most commonly asked Q&A's Time Complexity interview questions you can expect to be asked in your interview. Scroll Job Updates Interview Questions.

---

Answer :-  Time complexity here is O(N).Beware that to print a string of length L it takes O(L) time though. Here the length of the string we are printing is always 2, so we may assume it takes constant O(1) time to print it.

Answer :- If you calculate the number of times we print "Hi" here, you will get N * (1 + N) / 2 (Hint: use formula for the sum of arithmetic sequence). You can write it as N2/2 + N/2 which is O(N^2).

Answer :- This is a tricky one. Because there are two nested loops, you may think it's O(N^2). But note that p increases maximum about N - 5 times, so the inner loop executes maximum O(N) times, and the total time complexity is also O(N). Time complexity like this is what often called amortized time complexity. Here, amortized total number of times inner loop executes is O(N).

Answer :- Here we go only until I x | ≤ N, so until about square root of N. The time complexity here is O(n^(1/2)) - square root of N.

Note that this code also checks whether N is prime or not, and is based on the fact that all non-prime numbers have at least one divisor less or equal to its square root.

Answer :- It's often more difficult to analyze time complexity of recursive functions. Here, time complexity is O(N) and this code is a way to calculate the sum of the values of array a.

Answer :- Here, recursive function calculates some weird value over the array. What's important here is that this code runs in O(NlogN) time. To understand why, you may see that it's similar to Merge Sort, and learn how the complexity of Merge Sort is calculated.

Answer :- This is language dependent, but in Java strings are immutable, so each time you append to the string, new string object is created. Because of this, this code runs in O(N^2) time. If you don't fully understand this, be sure to read about strings and immutability in Java. Also read about appends to the strings in your language!

Answer :- This is a difficult one, and shouldn't occur at the interviews, but it's also a fun one. Here, the inner loop is executed N + (N/2) + (N/3) + ... times. We can rewrite it as Nx (1+1/2+1/3+ ...), and with the formula for the sum of harmonic series, we will get O(NlogN) runtime.