The Gateway to Computer Science Excellence
+1 vote
91 views

Correct answer is A

in Algorithms by (177 points) | 91 views
0
what is the problem with that answer?
0
a) i loop iterating from N to 1
and for each i => j loop iterating 0 to (N-1), i.e., N times for each i value.
so, O($N^2$)
0
Can u please explain how you got it
0
Second function???
0
b) i loop is iterating with value, 1, 2, 4, 8, 16 , ...., $2^N$

so, O(N).
+1
@Soumya pow() is constant operation=> O(1)
&, loop is iterating till 'max' => O(n)
0

Ans. D

 

a) O(n2)

b)

  • for loop : O(logN) 
  • depends on the implementation of pow() function, the complexity changes. It can be O(n) or O(log N).

So the only option that makes sense is the D

 

0

For second program,

for(i=0;i<K;i=i*2) ====> O(log2K)

in the place of K, we have 2n ===> O(n)

 

depends on the implementation of pow() function

they didn't mention about it, ===> take it as O(1)

0

@naveen Kumar 3

How 1,2,4,8......2^n leads to O(N)?

 

@shaik

 

for(i=0;i<K;i=i*2) ====> O(log2K)

in the place of K, we have 2n ===> O(n)

 

In above 2 points,if it's k in loop it's O(LOGK) 

and how if 2^n then it's O(N)?

0

if it's k in loop it's O(LOGK) 

and how if 2^n then it's O(N)?

O( log2K) = O( log2(2N)) = O(N)

0

How 1,2,4,8......2^n leads to O(N)?

$2^0$ , $2^1$ , $2^2$ , $2^3$ ,..., $2^N$ ===> N terms.

0

nag.swarna

If you're adding a test-series question, you've to specify the name of the test-series from where you took this qs.

0
Thanks Naveen

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,473 answers
195,393 comments
100,370 users