Register

GO Classes DPP | GATE DA | Python & DSA | Binary Halving

130 views
0 0 votes

What is the order of growth of $\texttt{foo}$ in terms of $\texttt{n}$, where $\texttt{n}$ is the length of $\texttt{lst}$?

Assume that slicing a list and calling $\texttt{len}$ on a list can both be done in constant time.

def foo(lst, i):
    mid = len(lst) // 2
    if mid == 0:
        return lst
    elif i > 0:
        return foo(lst[mid:], -1)
    else:
        return foo(lst[:mid], 1)
  1. $\mathrm{\Theta(1)}$
  2. $\mathrm{\Theta(log n)}$
  3. $\mathrm{\Theta(n)}$
  4. $\mathrm{\Theta(n log n)}$
  5. $\mathrm{\Theta(n²)}$

2 Answers

0 0 votes

In every recursive call, the function keeps only half of the list.

$\texttt{foo(lst[mid:], -1)}$

or:

$\texttt{foo(lst[:mid], 1)

So the input size changes like this:

$\texttt{n -> n/2 -> n/4 -> n/8 -> ... -> 1}$

The number of times we can divide $n$ by $2$ before reaching $1$ is $log(n)$.

Since each call does constant work, the total order of growth is:

$\mathrm{\Theta(log n)}$

Therefore, the correct option is B.

Voting & Accepting an answer helps improve the community
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

0 0 votes
2 2 answers
185
185 views
GO Classes asked Jul 4
185 views
GO Classes DPP | GATE DA | Python & DSA | Bubble Pass
What is the order of elements after the first pass of bubble sort algorithm?$\texttt{[5, 99, 1, 36, 4, 2]}$$\texttt{[1, 2, 4, 5, 36, 99]}$$\texttt{[5, 2, 1, 36, 4, 99]}$$...
1 1 vote
2 2 answers
116
116 views
GO Classes asked Jul 4
116 views
GO Classes DPP | GATE DA | Python & DSA | Sorting Complexity
Select all sorting algorithms that run in worst-case cost $\text{Θ(n log n)}$.HeapSortInsertionSortMergeSortQuickSort
2 2 votes
2 2 answers
122
122 views
GO Classes asked Jul 4
122 views
GO Classes DPP | GATE DA | Python & DSA | Selection Passes
Selection sort works in a series of passes over an array. Choose the answer that shows how this array will appear after the first two passes of selection sort.Original ar...
1 1 vote
2 2 answers
115
115 views
GO Classes asked Jul 4
115 views
GO Classes DPP | GATE DA | Python & DSA | Search Comparisons
How many comparisons will binary search be expected to perform to find one member of a list of $1000$ sorted numbers?$999$Approximately $20$Approximately $30$Approximatel...