Register

GO Classes 2024 | IIITH Mock Test 5 | Question: 31

• retagged by
292 views
2 votes
2 votes

Suppose we have a set of $n$ values. There are always at least one negative value and at least one positive value in the set.

What is the worst case time complexity to find FIRST negative value of set?

  1. If values are stored in an array and arranged in ascending order then it takes $\theta(n)$ in worst case.
  2. If values are stored in an array and arranged in descending order then it takes $\theta(n)$ in worst case.
  3. If values are stored in a linked list (only head is known)and arranged in ascending order then it takes $\theta(n)$ in worst case.
  4. If values are stored in a linked list (only head is known) and arranged in descending order then it takes $\theta(n)$ in worst case.
• retagged by
User Avatar

1 Answer

4 votes
4 votes

If values are stored in an array then

  • for ascending order it just takes $\theta(1)$ because the very first value is always first negative value.
  • for descending order it takes $\theta(\log n)$ because we can apply binary search to find first negative.

If values are stored in a linked list then

  • for ascending order it just takes $\theta(1)$ because the very first value is always first negative value.
  • for descending order it takes $\theta(n)$ because we can not apply binary search to find first negative.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

335
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
335 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 23
Which of the following is/are TRUE?In the worst case, merge sort runs in $O\left(n^2\right)$ time.Depth-first search of a graph is asymptotically faster than ... a binary search tree leaves the same tree as inserting $y$ and then $x$.
User Avatar
250
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
250 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 32
Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distance in ... $(u, v)$, we have $d[v]=d[u]+1$
User Avatar
Link Copied!