What is the time complexity T(n) of the nested loops
below? For simplicity, you may assume that n is a power of
2. That is, n = 2k for some positive integer k.
:
i = n;
while (i >= 1){
j = i;
while (j <= n) {
<body of the inner while loop > //
Needs (1).
j = 2 * j;
}
i = i/2;
}
:
- 2 Answers
- 14635 Views
- I also Faced
- E-Mail Answers
Answer Posted / arefe
hello I'm not sure about what I'm going to say . please tell me if you think it's wrong.
at first let's write some steps of it .
1) i = j = n
2) i = n/2 , j = n/2 --> j = n
3) i = n/4 , j = n/4 --> j = n/2 --> j = n
4) i = n/8 , j = n/8 --> j = n/4 --> j = n/2 , j = n
.
.
.
now if we count ,
the number of n , which j is equal to is log(n) ,
the number of n/2 , which j is equal to is log(n)-1 ,
the number of n/4 , which j is equal to is log(n)-2 ,
the number of n/8 , which j is equal to is log(n)-3 ,
and so on ,
so the result is summation log(n) - i , which i is from 0 to log(n) ,
we write log(n) out of Sigma and multiple it with log(n) + 1,( if we write Sigma term we have log(n) +1 , log(n))
and summation i , which i is from 0 to log(n) , is equal to (log(n)+1)(log(n))/2
| Is This Answer Correct ? | 0 Yes | 0 No |
Post New Answer View All Answers
How does C pass variables to a function ?
Write a java program to print the subsets of a string
What a test plan contains
which topics are come from quizs
1.orders for a computer are summarized by the additional features and are requested as follows; Proportion of order No features 0.3 One feature only 0.5 More than one feature 0.2 find; 1. what is the probability that an order requests at least one feature? 2. what is the probability that an order does not request more than one feature?
Net app interview questions ============================ . Storage Fundamentals: - what is Raid? What are different kind of Raids? - Difference between all of Raids , Advantage of one raid over other - What are FCP & ISCSI, Difference between them. - FC Topologies, Iscsi commands - How to mount a Lun on Windows/Linux - NFS and CIFS - Difference between SAN, NAS and DAS - Different Backup methodologies, Snapshot, mirror, Disaster Recovery, High Availability, Cluster concepts 2. Network Fundamentals: - TCP/IP and ISO/OSI layers - What is DHCP, DNS, SNMP, Router, Hub, Switch, HTTPS , HTTP, telnet , ssh, rsh - Different SNMP versions (V1, V2, V3) - SNMP traps - Ipv4 and Ipv6 addressing 3. Database: - SQL queries, Joins (may ask you to write queries with complex joins) - Aggregate functions - Schemas, Tables, views (create, delete, alter, drop etc) 4. Testing - Bug tracking process, Types of Bugs - Difference between priority and Severity of Bug - Your best bug , what will you do when your bug is not fixed/rejected etc. - What is Functionality/Sanity/Stress/Upgrade & revert/Performance/negative/Release test/regression tests. How you have done these in your past projects. - Black box testing, grey box testing - May ask to write test cases on a given scenario - What is test plan and test summary/strategy document. Different sections in these documents. - SDLC, Test Lifecycle and approach to test a product (Given a product what different kind of testing you will do) 5. Perl ( in addition, you may be asked to write scripts on below areas) - Regular expressions - File/Directory Handling - Scalars, Arrays and Hashes - Packages and Modules - Use and require statements - Go through Net::Telnet, Net::SNMP, Net::SSH modules in perl
who is the judge in case of the auditor has raised an NCR against an auditee? who should decide weather this NCR is acceptable and the auditee has to accept?
what is difference between shell commands and shell scripting commands or both r same?
sir, please send me the last three years exam papers conducted by CPCL- RECRUITMENT EXAM FOR Recruitment of Engineer ELECTRICAL ENGINEERING. A Soon as possible. i would be greatfull to u
What is the weight of a foot square block of bronze.
write an algorithm in O(n) time for finding the kth smaalest element form an array of n elements , where n and k are entered by user
Calculate the interstage pressure ratio per stage for a two stage compressor if the overall pressure ratio is 10.
Why do large ships like aircraft carriers not sink despite weighing several thousand tonnes?
hi,i came to US to pursue my masters in computer information technology.Can i do my masters the first 6months in US and the rest 9 months course from INDIA through online education
Explain work?
