The Gateway to Computer Science Excellence

+1 vote

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$)

and for each i => j loop iterating 0 to (N-1), i.e., N times for each i value.

so, O($N^2$)

0

Ans. D

a) O(n^{2})

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(log_{2}K)

in the place of K, we have 2^{n} ===> 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(log_{2}K)

in the place of K, we have 2^{n} ===> 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( log_{2}K) = O( log_{2}(2^{N})) = O(N)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,473 answers

195,393 comments

100,370 users