time complexity

dondora

hi there.
this is my homework. I've been trying to get some result but things
haven't been gone well.
Those are the nested loop. And What I have to do is to get time
complexity T(n) of the nested loop assuming n=2^k.

---------------------------------------------------------------------------------------------------------
for(i = 0; i<=n; i++) {
j = n;
while( j>= 1) {
<body of the while loop // Needs Ï´(1)
j = j/2;
}
}
---------------------------------------------------------------------------------------------------------

What I got is T(n) = n{1 + (k+1)(Ï´(1) + 1_} assuming j=n and j=j/2
and Ï´(1) are unit operations.
So I did try to solve my result to get a neat expresion.
that's what I did
n=2^k = lg(n)=k
T(n) = n{1 + (k+1)(Ï´(1) + 1)}
= n{1 + (lg(n) + 1)(Ï´(1) + 1)}
= n{1 + lg(n)Ï´(1) + lg(n) + Ï´(1) + 1} // by distribution law
and
= n{1 + lg(n)Ï´(1) + lg(n) + Ï´(1)}
= n{1 + lg(n)Ï´(1) + Ï´(lg(n))}
= n{1 + Ï´(lg(n)) + Ï´(lg(n))}
= n{Ï´(lg(n)) + Ï´(lg(n))}
= n{Ï´(lg(n))} = nÏ´(lg(n)) = Ï´(nlg(n))

is that right? I wanna know where it's right or not.
I guess it has something wrong. So I need your help.
I appreciate your generous help.
ps : don't say to me 'do you own homework'. I already tried many times.

Sep 16 '07 #1

Subscribe Post Reply

2724

xhli

well, I think the result is correct.

dondora å†™é“:

hi there.
this is my homework. I've been trying to get some result but things
haven't been gone well.
Those are the nested loop. And What I have to do is to get time
complexity T(n) of the nested loop assuming n=2^k.

---------------------------------------------------------------------------------------------------------
for(i = 0; i<=n; i++) {
j = n;
while( j>= 1) {
<body of the while loop // Needs Ï´(1)
j = j/2;
}
}
---------------------------------------------------------------------------------------------------------

What I got is T(n) = n{1 + (k+1)(Ï´(1) + 1_} assuming j=n and j=j/2
and Ï´(1) are unit operations.
So I did try to solve my result to get a neat expresion.
that's what I did
n=2^k = lg(n)=k
T(n) = n{1 + (k+1)(Ï´(1) + 1)}
= n{1 + (lg(n) + 1)(Ï´(1) + 1)}
= n{1 + lg(n)Ï´(1) + lg(n) + Ï´(1) + 1} // by distribution law
and
= n{1 + lg(n)Ï´(1) + lg(n) + Ï´(1)}
= n{1 + lg(n)Ï´(1) + Ï´(lg(n))}
= n{1 + Ï´(lg(n)) + Ï´(lg(n))}
= n{Ï´(lg(n)) + Ï´(lg(n))}
= n{Ï´(lg(n))} = nÏ´(lg(n)) = Ï´(nlg(n))

is that right? I wanna know where it's right or not.
I guess it has something wrong. So I need your help.
I appreciate your generous help.
ps : don't say to me 'do you own homework'. I already tried many times.

Sep 17 '07 #2

by: Edg Bamyasi | last post by:

This Is A Late Cross Post from comp.lang.python. It seems the mistery is deeper then i expected. What is the running time of conactination on character strings. i.e. >> joe="123" >>...

Python

Chat: C# 3.0 Language Enchancements, September 22nd @ 1pm Pacific Time

by: Scott Nonnenberg [MSFT] | last post by:

This is really exciting stuff. We'll see you there! It might be a good idea to do some background reading before you show up. :0) C# 3.0: http://msdn.microsoft.com/vcsharp/future/ The LINQ...

.NET Framework

ADP Ready for Prime Time?

by: Neil Ginsberg | last post by:

A while back I posted a message re. using an ADP file with a SQL Server back end as opposed to MDB file with linked tables, thinking that the ADP file would be less problematic. The input I got was...

Microsoft Access / VBA

Time Complexity

by: davide.sammartino | last post by:

Hi, when the processor meet this instruction i >4; the operation, inside the processor, is computed constantly or linearly in time?

C / C++

Time complexity of size() for std::set

by: Lionel B | last post by:

Hi, Anyone know if the Standard has anything to say about the time complexity of size() for std::set? I need to access a set's size (/not/ to know if it is empty!) heavily during an algorithm...

C / C++

Delete from a std::set in amortized constant time

by: desktop | last post by:

In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is a pointer to an element can be done in amortized constant time. I guess that is not worst case since std::set is...

C / C++

amortized analysis time complexity problem

by: chits12345 | last post by:

Hi all Is there anybody who can solve this problem? This is not a easy problem. Problem: Assume that George(S,X) is a function that returns a Boolean value, where S is a stack, and that...

C / C++

Time Complexity of String Operations

by: youtoo | last post by:

It has been extensively discussed the time complexity (quadratic) of string concatenation (due to string's immutability). But what is: == the time complexity of string indexing? Is it constant?...

Python

How to turn on java script in a villaon keypad mobile phone

by: Charles Arthur | last post by:

How do i turn on java script on a villaon, callus and itel keypad mobile phone

Java

Merging data from multiple Excel files

by: ryjfgjl | last post by:

In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...

Data Management

Migrating Website to Cloud - Emmanuel Katto

by: emmanuelkatto | last post by:

Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel

General

Navigating the Data Structures and Algorithms (DSA)

by: BarryA | last post by:

What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...

Algorithms / Advanced Math

Is that possible of reading the .csv file in column wise and the column have different lengths ?

by: Sonnysonu | last post by:

This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...

C / C++

What is ONU?

by: marktang | last post by:

ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...

General

Problem With Comparison Operator <=> in G++

by: Oralloy | last post by:

Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...

C / C++

Maximizing Business Potential: The Nexus of Website Design and Digital Marketing

by: jinu1996 | last post by:

In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...

Online Marketing

The easy way to turn off automatic updates for Windows 10/11

by: Hystou | last post by:

Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

Windows Server

time complexity

Similar topics