ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

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 02:48 PM.

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.

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 03:00 PM.
Reason: Forgot to close tag

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)?

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.