Register

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

• edited by
518 views

2 Answers

8 8 votes

$\Theta(\sqrt{N})$.


 

We know that each iteration of the for loop takes constant time, so we need to figure out how many iterations of the for loop occur; let this mount be $k$. At every step, $i$ increments by 1 so we are essentially accumulating in $s=1+2+3+\cdots+k$ until $s>N$.


 

Therefore, we want to solve for $1+2+3+\cdots+k=N$ which approximately simplifies to $k^2=N$, which we solve to obtain $k=\sqrt{N}$.


 

Our runtime is determined by $k$ which is therefore $\Theta(\sqrt{N})$.

1 1 vote
Let c=1 2 4 7...n be the series. Subtracting it from itself by skipping first term like we do in agp, we get 0=1 1 2 3 4...k - n hence we can say n is approx squared of k, which means k is root of n.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes Test Seri...Next → · GO Classes Test Seri...
← Previous in category · GO Classes Test Seri...Next in category → · GO Classes Test Seri...
Position:
Show:

Related questions

1 1 vote
2 2 answers
484
484 views
GO Classes asked Sep 16, 2024
484 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
508
508 views
GO Classes asked Sep 16, 2024
508 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...
2 2 votes
1 1 answer
431
431 views
GO Classes asked Sep 16, 2024
431 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)$
1 1 vote
1 1 answer
283
283 views
GO Classes asked Sep 16, 2024
283 views
GO Classes Test Series | Data Structures and Algorithms | Topic Wise Test 2 | Question: 15
What is the time complexity of following code?def fun(n): count = 0 i = n while i 0: for j in range(i): count += 1 i //= 2 return count$\Theta(N \log N)$$\Theta(N)$$\The...