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
- 15230 Views
- I also Faced
- E-Mail Answers
Answer Posted / muhammad ijaz khan
The outer loop divides the working area in half in each
iteration. So the running time of this algorithm is
proportional to the number of times n can be divided by 2.
The inner loop will be executed unlimitted time. So
the time complexity of the outer loop will be the function
of ln and the total time is: T(n)= n*ln n
| Is This Answer Correct ? | 10 Yes | 20 No |
Post New Answer View All Answers
I want to prepare for PSU's bt i dont know how many PSU's are open for computer science students and what is the competition level for these. So if anybody knows this please guide me through this.
good morning! can u briefly explain the concept of syllolism and wat it mean?
what two ways you can use to ensure that visual basic does not allow uncleared variables?
how can i install windows-xp operating system in single time to 50 computersconnected in a LAN.
difference between w2k and win xp....
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
how do we calculate physical address if logical address is given in the question?
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
Hi i want some previous interview questions and answers for KVB Bank.
Hi i'm richa piplani applied for ATC(IT) if u have the syllabus & old question papers forward me.I will be very much thankful to you. piplani.richa@gmail.com and sonu_pips@yahoo.co.in
#include
when did actually oil exploration start
I am going to HAL Online test for Computer Science. Can you please mail me the model question papers ?
how will u recieve an std idoc from sendor->reciever
I'm currently placed in Lahore Pakistan. where can i do Microsoft certification. let me know the best place to do.?
