Solved

RunTime Complexity

Posted on 2007-04-09
21
1,343 Views
Last Modified: 2008-02-01
Hi there Buddies.
I've already answered the first 2 Functions But I wanna know if my answers are true
But I couldnt find a solution for the 3rd function
Here is the Question
1. Let n=2k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2k) = k   ,,, so It’s O(k)
Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of 2k is 2k*log(2k)  = 2k * k  ,,, so It’s O(2k)
Prod =  2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21   = 2k  -  2


Thanks
0
Comment
Question by:nikorba
  • 7
  • 6
  • 4
  • +2
21 Comments
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
Comment Utility
I gather that 2k means 2^k or 2**k

> Second Function :
> Complexity as a function of n  is n*log(n)
I don't think that's right
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
> if ((j % Math.Sqrt(n))==0)
How many times would this be true?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Are you saying Prod is less than 2k?
0
 
LVL 12

Expert Comment

by:Sinoj Sebastian
Comment Utility
Sorry, not an answer, just a point

log2(2k) = 1+log2(k)  {not k; log2(2^k)=k}
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
Hi there ,,, well , there are some mistakes in the Question ,,, because I copied it from the word Document ,,, so I thought that the exponent will appear correctly ...I will fix it now
Here is the Question
1. Let n=2^k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2^k) = k   ,,, so It’s O(k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of k is 2^k*log(2^k)  = (2^k )* k  ,,, so It’s O(2^k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Thanks
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 65 total points
Comment Utility
>> Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Not really (as ozo already noted).

           2^(k(k + 1)/2)

is more like it ... can you explain why ?


>> Complexity as a function of n  is n*log(n)

That's not correct ... you have nested loops of the same type as in the first function ... what does that give complexity wise ?
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
OZo didn't saw my 2nd comment :)
I think the 1st two functions are correct
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> I think the 1st two functions are correct

No, see my previous post ...
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
>>>No, see my previous post ...

I saw it,,,
try to solve it numerically
try a number with the F1
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> try to solve it numerically
>> try a number with the F1

What do you mean ?

You said :

      Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

And that's simply not true ... (see my earlier post)
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
there were answers
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
I still think that my answers were right ,,, that;s it
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Then I wonder why you were asking our help, if you can't accept what we have to say ?
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
I appreciate ur help ,,, at first I wasnt sure about my answers so I asked u
but after a while the I asked the lecturer and he said my answers were right
I really thank u so much for ur help but that what happened
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
If your teacher says that this :

    Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

is correct, then he's wrong :)

2^(k)  -  2 is smaller than 2^(k), while Prod is a lot larger. How can those two be equal ?

Try filling in k=3 for example. You say that :

    Prod = 2^3 * 2^(2) * 2^(1)  = 2^(3)  -  2
    Prod = 2^6  = 2^3  -  2
    Prod = 64  = 6

How can 64 be equal to 6 ???
0
 
LVL 20

Expert Comment

by:Venabili
Comment Utility
OK - this is one of these "why the hell I recommended delete" :)

So what we do with the question?
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
If nikorba still wants our help, then I'll be glad to provide that ... if not, then this question can be PAQ'd for ozo as he was first :)
0
 
LVL 2

Author Comment

by:nikorba
Comment Utility
I'm sorry I discovered that I was wrong
sorry everyone :)
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now