how to calculate the time complexity of a given algorithm?
pls give exaples..mainly for the coplexities such as O(log
n),O(n log n)...
Answer Posted / s v s pradeep
Generally 0(log n) and 0(n log(n)) will come into picture
if u are dealing with the programs that have for loops
(where the increment is divided or multiplied), functional
blocks.
Eg. for(i=0;i<n;i=i++)
for(j=0;j<n;j=j*2)
......
Here in this case the inner loop complexity is 3n+2 where
the outer loop complexity will be in logarithm terms
because every time when we increment i value the, i is
multiplied by 2 so the no of iterations will be reduced ..
so when the iterations are reduced then we will get log(n)
so, for the above example the complexity will be 0(n log(n))
n-- for the outer loop and log(n) is for inner loop.
so multiply the no of times innerloop will be executed for
the outer loop. so n*log(n).
So the time complexity will be 0(n log(n)).
..
Is This Answer Correct ? | 14 Yes | 7 No |
Post New Answer View All Answers
What is || operator and how does it function in a program?
Tell us something about keyword 'auto'.
What is a class c rental property?
In this problem you are to write a program that will cut some number of prime numbers from the list of prime numbers between 1 and N.Your program will read in a number N; determine the list of prime numbers between 1 and N; and print the C*2 prime numbers from the center of the list if there are an even number of prime numbers or (C*2)-1 prime numbers from the center of the list if there are an odd number of prime numbers in the list.
Explain what happens if you free a pointer twice?
What is calloc() function?
What is union and structure in c?
What is meant by high-order and low-order bytes?
what is the structure pointer?
Do character constants represent numerical values?
Why do we use null pointer?
The OS is a program that uses various data structures. Like
all programs in execution, you can determine the
performance and other behavior of the OS by inspecting its
state - the values stored in its data structures. In this
part of the assignment, we study some aspects of the
organization and behavior of a Linux system by observing
values of kernel data structures exposed through the /proc
virtual file system.
The /proc virtual file system:
Linux uses the /proc file system to collect information
from kernel data structures. The /proc implementation
provided with Linux can read many different kernel data
structures. If you cd to /proc on a Linux machine, you will
see a number of files and directories at that location.
Files in this directory subtree each corresponds to some
kernel data structure. The subdirectories with numeric
names contain virtual files with information about the
process whose process ID is the same as the directory name.
Files in /proc can be read like ordinary ASCII files. You
can open each file and read it using library routines such
as fgets() or fscanf(). The proc (5) manual page explains
the virtual files and their content available through
the /proc file system.
Requirements in detail:
In this part, you are asked to write a program to report
the behavior of the Linux kernel. Your program should run
in two different versions. The default version should print
the following values on stdout:
• Processor type
• Kernel version
• The amount of memory configured into this computer
• Amount of time since the system was last booted
A second version of the program should run continuously and
print lists of the following dynamic values (each value in
the lists is the average over a specified interval):
• The percentage of time the processor(s) spend in
user mode, system mode, and the percentage of time the
processor(s) are idle
• The amount and percentage of available (or free)
memory
• The rate (number of sectors per second) of disk
read/write in the system
• The rate (number per second) of context switches in
the kernel
• The rate (number per second) of process creations
in the system
If your program (compiled executable) is called proc_parse,
running it without any parameter should print out
information required for the first version. Running it with
two parameters "proc_parse
How can I copy just a portion of a string?
write a program in c language to print your bio-data on the screen by using functions.
Which of these functions is safer to use : fgets(), gets()? Why?