Register

GO Classes DPP | GATE DA | Python & DSA | Nested Calls

122 views
1 1 vote

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
    while i <= n:
        sum += i**3
        i += 1
    return sum
  1. Constant
  2. Logarithmic
  3. Linear
  4. Quadratic
  5. Exponential
  6. None of these

2 Answers

1 1 vote

In $\texttt{bar(n)}$, the outer loop runs $\texttt{n}$ times.

In each iteration, $\texttt{biz(n)}$ is called.

In $\texttt{biz(n)}$, the loop also runs $\texttt{n}$ times. The expression $\texttt{i**3}$ does not make the loop cubic, because $\texttt{i}$ is still increasing by $\texttt{1}$.

bar loop $: \text{n}$ times
biz loop $: \text{n}$ times

Total $\mathrm{= n * n = n^2}$

Therefore, the order of growth is Quadratic.

Correct Option: D

0 0 votes 
def bar(n):
    i, sum = 1, 0
    while i <= n:        # runs n times
        sum += biz(n)    # takes O(n) time
        i += 1
    return sum
 
def biz(n):
    i, sum = 1, 0
    while i <= n:        # runs n times
        sum += i**3
        i += 1
    return sum

$N*O(N) = O(N^2)$

Answer: D. Quadratic

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
154
154 views
GO Classes asked Jul 6
154 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
125
125 views
GO Classes asked Jul 6
125 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
119
119 views
GO Classes asked Jul 6
119 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
110
110 views
GO Classes asked Jul 6
110 views
GO Classes DPP | GATE DA | Python & DSA | Halving Input
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}...