Register

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

113 views
1 1 vote

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

Assume slicing a list and calling $\texttt{len}$ both take 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)

What is the tight order of growth?

  1. $\Theta(\log n)$
  2. $\Theta(n)$
  3. $\Theta(n \log n)$
  4. $\Theta(n^2)$

2 Answers

1 1 vote

In each call, only one recursive call is made.

The input list is reduced to half:

$n \rightarrow n/2 \rightarrow n/4 \rightarrow n/8 \rightarrow ... \rightarrow 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 complexity is:

$\Theta(\log n)$

Correct Answer: A

0 0 votes
Each step reduces the remaining search space by half. That gives us logarithmic time.
For tight order of growth, we can see that it cannot take less than logarithmic time because the halving is never shortcircuited to constant work.
And it will never take more than logarithmic time because each step definitely halves the search space.

So we get $\Theta(\log n)$

Answer: A
• edited by
Voting & Accepting an answer helps improve the community
Answer:
← 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

3 3 votes
2 2 answers
157
157 views
GO Classes asked Jul 6
157 views
GO Classes DPP | GATE DA | Python & DSA | Membership Cost
Let $\text{L}$ contain $\text{N}$ items. What is the Big-O efficiency of the following function?def countSquares(L): count = 0 for item in L: square = item 2 if item != s...
1 1 vote
2 2 answers
129
129 views
GO Classes asked Jul 6
129 views
GO Classes DPP | GATE DA | Python & DSA | Dependent Loops
Let $\text{N = n}$. What is the Big-O efficiency of the function below?def f1(n): ret = [] for i in range(n): for j in range(i + 1, n): ret.append(i + j) return ret$\math...
1 1 vote
2 2 answers
123
123 views
GO Classes asked Jul 6
123 views
GO Classes DPP | GATE DA | Python & DSA | Tricky Loop
Describe the order of growth of the function below.def bonk(n): sum = 0 while n >= 2: sum += n n = n / 2 return sumConstantLogarithmicLinearQuadraticExponentialNone of th...
1 1 vote
2 2 answers
126
126 views
GO Classes asked Jul 6
126 views
GO Classes DPP | GATE DA | Python & DSA | Nested Calls
What is the order of growth of $\texttt{bar}$ in terms of $\texttt{n}$?def bar(n): i, sum = 1, 0 while i <= n: sum += biz(n) i += 1 return sum def biz(n): i, sum = 1, 0 w...