Bissoy.com
Doctors Medicines MCQs Q&A

What is the complexity of the following code? sum=0;        for (i=1; I <= n; i*=2)                 for(j=1; j<=n;j++)                                 sum++;

What is the complexity of the following code? sum=0;        for (i=1; I <= n; i*=2)                 for(j=1; j<=n;j++)                                 sum++; Correct Answer O(n log n)

Code

Time complexity

sum = 0

O(1)

for (i=1; I <= n; i*=2)

O(logn) because I is incremented exponentially and loop will run for less number of times than n.

for(j=1; j<=n; j++)

O(n) because j is incremented linearly and loop will run for n number of times.

sum++

O(1)

 

Total time complexity = O(n×logn)

Important Point:

In original ISRO CS 2020, and extra data was present “Which of the following is not a valid string?”

Which made this question ambiguous and hence excluded from evaluation.

Related Questions

Which of the following command options are displayed when you use the Router# show frame-relay ? command?
1. dlci
2. neighbors
3. lmi
4. pvc
5. map
Which of the following commands will display the current IP addressing and the layer 1 and 2 status of an interface?
1. show version
2. show protocols
3. show interfaces
4. show controllers
5. show ip interface
To enable EIGRP, which of the following would you use?
1. Router1(config-if)# ipv6 ospf 10 area 0.0.0.0
2. Router1(config-if)# ipv6 router rip 1
3. Router1(config)# ipv6 router eigrp 10
4. Router1(config-rtr)# no shutdown
5. Router1(config-if)# ipv6 eigrp 10
Which two of the following commands will place network 10.2.3.0/24 into area 0?
1. router eigrp 10
2. router ospf 10
3. network 10.0.0.0
4. network 10.2.3.0 0.0.0.255 area0
5. network 10.2.3.0 0.0.0.255 area 0
Which three commands can be used to check LAN connectivity problems on a router?
1. show interfaces
2. show ip route
3. tracert
4. ping
5. dns lookups
You need to allow one host to be permitted to attach dynamically to each switch interface. Which two commands must you configure on your catalyst switch to meet this policy?
1. Switch (config-if) # ip access-group 10
2. Switch (config-if) # switchport port-security maximum 1
3. Switch (config) # access-list 10 permit ip host 1
4. Switch (config-if) # switchport port-security violation shutdown
5. Switch (config) # mac-address-table secure
Consider a fully-associative data cache with 32 blocks of 64 bytes each. The cache uses LRU (Least Recently Used) replacement. Consider the following C code to sum together all of the elements of a 64 by 64 two-dimensional array of 64-bit double-precision floating point numbers. double sum (double A [64] [64] ) { int i, j ; double sum = 0 ; for (i = 0 ; i < 64; i++) for (j = 0; j < 64; j++) sum += A [i] [j] ; return sum ; } Assume all blocks in the cache are initially invalid. How many cache misses will result from the code?
The question below is followed by statements I, II, and III. You have to determine whether the data given in the statement is sufficient for answering the question. You should use the data and your knowledge of Mathematics to choose the best possible answer. The difference between the compound interest and simple interest on a certain sum at a certain rate of interest per annum for two years is 204.20. What is the amount received on the sum of compound interest at the same rate of interest at the end of three years. I. The difference between the compound interest and the simple interest on the sum for three years is 804.258. II. The sum becomes Rs. 14528 at the end of one year. III. The compound interest on the sum for two years is 7% more than the simple interest on the sum for two years.
Consider the following statements:
1. Section 34 of Indian Penal Code requires two persons whereas Section 149 of Indian Penal Code require five persons.
2. Section 34 of Indian Penal Code requires common intention, whereas Section 149 of Indian Penal Code requires common object
3. Section 34 of Indian Penal Code and Section 149 of Indian Penal Code both require presence of a prior consent
4. Section 34 of Indian Penal Code and section 149 of Indian Penal Code. Both create specific offence
Which of the above statements are correct?
What two multicast addresses does OSPFv3 use?
1. FF02::A
2. FF02::9
3. FF02::5
4. FF02::6