Register

GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 15

• edited by
266 views

1 Answer

2 2 votes

Answer is Option B

Unroll the inner for loop .

Time complexity will be $n+\frac{n}{2}+\frac{n}{4}+.........+\frac{n}{2^{k}}$ where $k=\log _{2}n$

T.C = $\Theta \left ( 2^{k} \right ) = \Theta \left ( n \right )$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes CS Test S...Next → · GO Classes Test Seri...
← Previous in category · Hashing: Quadratic P...Next in category → · GO Classes Test Seri...
Position:
Show:

Related questions

1 1 vote
2 2 answers
454
454 views
GO Classes asked Sep 16, 2024
454 views
GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 6
Consider $\text{Iterated logarithm}$ of $n,$ written $\log^\ast n$ (usually read "$\log$ star $n$"), is the number of times the logarithm (base $2$) function must be iter...
5 5 votes
1 1 answer
483
483 views
GO Classes asked Sep 16, 2024
483 views
GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 7
Consider the following $\text{C}$ function:def fun1(n): q = 0 for i in range(1, n): p = 0 j = n while j 1: p += 1 j = j // 2 k = 1 while k < p: q += 1 k = k * 2 return q...
6 6 votes
2 2 answers
497
497 views
GO Classes asked Sep 16, 2024
497 views
GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 8
What will be the time complexity of following code?def mystery(N): i = 1 s = 1 while s <= N: i += 1 s = s + i$\Theta(\sqrt{N})$$\Theta(N)$$\Theta(\log N)$$\Theta\left((\l...
2 2 votes
1 1 answer
418
418 views
GO Classes asked Sep 16, 2024
418 views
GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 9
def fun(N): i = N while i 0: for j in range(i * 2): print("Hello World") i = i // 2$\Theta(N \log N)$$\Theta(N)$$\Theta(\log N)$$\Theta\left((\log N)^{2}\right)$