Hi,

Please guide me “What is meant by to estimate efficiency of algorithm asymptotically”?

I found that it means to measure the running time as the number of elementary steps (defined in any way) provided each such step takes constant time.


In my last thread

https://forum.allaboutcircuits.com/threads/how-there-are-eight-assignments-in-this-code.143907/

We tried to find the complexity by considering the number of assignments. Is there any other way to find complexity using elementary steps such that each step takes constant time.


Some body please guide me.

Zulfi.

 

yes, it is called Google and Wiki

https://en.wikipedia.org/wiki/Analysis_of_algorithms

you can also lookup Big-O notation.

number of clocks it takes to process one block of code is not important.
key here is to determine complexity in terms of order of magnitude based on how efficient code is.
if one can get result by running through list of instructions once, that is a very simple (and "efficient" case)
if getting result requires executing block of instructions many times, this is less efficient.
if the number of passes also depends on size of data block to be processed, this is even less efficient.

consider Bubble sort, for short data sets, Bubble sort is quite efficient.
but when you get in big data sets, pair of nested loops take toll...

goal here is to estimate how efficient code is when dealing with REALLY big data sets....

 

Please guide me “What is meant by to estimate efficiency of algorithm asymptotically”?

I found that it means to measure the running time as the number of elementary steps (defined in any way) provided each such step takes constant time.

It CAN mean to measure the running time, but it can also mean anything else. Other common metrics are space (memory), area (die space), and energy/power.

The basic idea is to find a relatively simple expression that estimates the value of the metric as the size of the problem grows arbitrarily large.

There are several definitions of algorithmic complexity, with "big-O" probably being the most commonly used.

 

yes, it is called Google and Wiki

https://en.wikipedia.org/wiki/Analysis_of_algorithms

you can also lookup Big-O notation.

number of clocks it takes to process one block of code is not important.
key here is to determine complexity in terms of order of magnitude based on how efficient code is.
if one can get result by running through list of instructions once, that is a very simple (and "efficient" case)
if getting result requires executing block of instructions many times, this is less efficient.
if the number of passes also depends on size of data block to be processed, this is even less efficient.

consider Bubble sort, for short data sets, Bubble sort is quite efficient.
but when you get in big data sets, pair of nested loops take toll...

goal here is to estimate how efficient code is when dealing with REALLY big data sets....

---
Hi, Thanks. You mean that the list of instruction can be considered as a single step. It looks logical.

Zulfi.

 

It CAN mean to measure the running time, but it can also mean anything else. Other common metrics are space (memory), area (die space), and energy/power.

The basic idea is to find a relatively simple expression that estimates the value of the metric as the size of the problem grows arbitrarily large.

There are several definitions of algorithmic complexity, with "big-O" probably being the most commonly used.

==
Hi Thanks.
God bless you.

Zulfi.