LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 03-01-2018, 01:08 PM   #1
zak100
Member
 
Registered: Jul 2009
Posts: 262

Rep: Reputation: 2
Running Time Question


Hi,
This is running time question. I have got following code snippet:

Code:
int count =0;
for(int i=n/2; i<=n; i++)
   for(int j=1; j+n/2<=n; j=j++)
       for(int k=1; k<=n; k=k*2)
          count++;
}
Q. What is the running time of above code?

I have tried to find the running time of each loop separately:
Code:
for(int i=n/2; i<=n; i++)
if n=4; then i=2, 3, 4
n=8; then i=4, 5, 6, 7, 8
slighly greater than half so running time is log n.

Now for:
Code:
for(int j=1; j+n/2<=n; j=j++)
if n=4: then j=1, 2,
n=8; then j=1, 2, 3, 4
Again log n.
And for:
Code:
for(int k=1; k<=n; k=k*2)
running time is also log n.

There running time = log n * log n * log n
=O(log(n)^3)

Is this correct. Some body please guide me.

Zulfi.
 
Old 03-01-2018, 01:31 PM   #2
keefaz
LQ Guru
 
Registered: Mar 2004
Distribution: Slackware
Posts: 6,230

Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
Quote:
Originally Posted by zak100 View Post
slighly greater than half so running time is log n.
I like it

Seriously, if I get the question. The running time is equal to loop iterations count, no?
 
Old 03-01-2018, 01:52 PM   #3
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 3,635

Rep: Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114
What do you mean 'j=j++'? https://en.m.wikipedia.org/wiki/Undefined_behavior
 
Old 03-01-2018, 03:46 PM   #4
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171
This very-familiar homework question is – as you know –*asking you to evaluate the "Big-O notation" of a particular process. You should come up with your own answer, and then be bold enough to turn it in.

Functionally speaking, you've basically got three situations of interest: either it's on the order of "n," or some power of "n," or some logarithm of "n." Beyond that, nobody really has too much reason to care.

"Padewan, above all, do not lack confidence."

Last edited by sundialsvcs; 03-01-2018 at 03:48 PM.
 
Old 03-02-2018, 12:11 PM   #5
zak100
Member
 
Registered: Jul 2009
Posts: 262

Original Poster
Rep: Reputation: 2
Hi,
Thanks for your responses.
I have provided you my solutions.Its not a homework.
Be bold enough to say 'yes' or 'no'. Its not earth shattering.

"Functionally speaking, you've basically got three situations of interest: either it's on the order of "n," or some power of "n," or some logarithm of "n."

Not so much helpful. You know its something similar to saying that a boolean variable has either a '0' or a '1' answer but I never knew your analogy.

Still looking for some hints.

Zulfi.
 
Old 03-02-2018, 04:00 PM   #6
adunr
Member
 
Registered: Feb 2018
Location: Who knows?
Distribution: Slackware, OpenBSD, Arch
Posts: 33

Rep: Reputation: Disabled
Your original solution doesn't look correct. Remember that worst-case complexity doesn't tell you how long it takes to run an algorithm (or in any case, not directly), it tells you how much the running time would increase if n were to increase.

Both of these snippets are O(n):

Code:
for (i = 0; i < n; i++)
    foo();
and

Code:
for (i = 0; i < n/2; i++)
    foo();
That's because, in both cases, if we were to increase n by a certain factor, the running time of the algorithm would be increased by the same factor. That's why we colloquially say that we can "dispense with the constant" (hence, for example, both these snippets are O(1):

Code:
int foo(void) {
    x = x + 1;
}
and

Code:
int foo(void) {
    x = x + 1;
    x = x + 2;
    x = x + 3;
}
Logarithmic complexity looks very different, but the gist of it is that something runs in logarithmic time if, at every step, you reduce the solution space by a fixed proportion (think of binary search: it's logarithmic because, after each step, you've reduced the problem space by half).

Last edited by adunr; 03-02-2018 at 04:00 PM. Reason: Forgot to close tag
 
1 members found this post helpful.
Old 03-02-2018, 09:34 PM   #7
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 3,635

Rep: Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114
@OP: Once you fix your code, it will be O(n*n*sqrt(n))

PS: you might not know but it is a homework question

Last edited by NevemTeve; 03-02-2018 at 09:36 PM.
 
Old 03-03-2018, 01:11 PM   #8
zak100
Member
 
Registered: Jul 2009
Posts: 262

Original Poster
Rep: Reputation: 2
Hi,
Thanks for your responses.
<From adnur:
for (i = 0; i < n/2; i++)
foo();
>
Okay its O(n) because we are not dividing the problem size into half at each step.

<From NevenTeve:
Once you fix your code, it will be O(n*n*sqrt(n))>

I am redoing:
for(int i=n/2; i<=n; i++): if n=100 then i=50..100 => O(n)
for(int j=1; j+n/2<=n; j++): => O(n)
for(int k=1; k<=n; k=k*2):

if n= 16 then k= 1, 2, 4, 8, 16; this is also greater than log base 2 n which is 4. I have two questions:
i) Why its sqrt(n)?
ii) Can we take log(n) instead of sqrt(n)?

If some body has time, please reply me.

Zulfi.

Last edited by zak100; 03-03-2018 at 01:15 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Kali Question, Running latest version 2017.2 problems running Kismet. Mr_Robot Linux - Newbie 2 11-10-2017 07:24 AM
[SOLVED] total process time and time in present state(sleep/running/ uninterruptible). satyadev75 Linux - Server 1 05-16-2013 07:03 AM
Time is running out for me. ccalvin12 Linux - Software 1 08-05-2005 08:18 AM
Newbie question - running a script at boot time Napalm Llama Red Hat 8 04-19-2005 04:11 PM
Simple scripting question - running a command for a specified time FluoroAlien Programming 8 03-06-2004 01:33 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:12 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration