Asymptotic Notation

-


  • Running time of an algorithm, order of growth. 
  • Worst case.  
  • Running time of an algorithm  increases with the size of the input in the limit as the size of the input increases without bound.


Big-theta notation (a=b)

  • g(n) is an asymptotically  tight bound of f(n).
  • Asymptotically non negative/positive.
  • If g(n) is asymptotically negative then theta(g(n)) = empty. 



Example

1/2n2 - 3n= theta(n2).


Big O-notation (a<=b)

  • Asymptotic upper bound
  • Not tight bound 
  • Theta is stronger than O
  • O notation describe upper bound on every input.
  • We also have amortized analysis.[An amortized analysis is any strategy for analyzing a sequence of perations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive]
    ]





Example
The running time is O(n2) means there is a function f(n) that is O(n2) such that for any value of n, no matter what particular input of size n is chosen, the running time of that input is bounded from above by the value f(n).



Big-Omega notation (a>=b)

  • Asymptotic lowerbound




o-Notation



w-notation


Properties:

analogy to comparison of two real numbers, a, b.




Comments

Post a Comment

Popular posts from this blog

JDBC Hive Connection fails : Unable to read HiveServer2 uri from ZooKeeper

-
Image
I have been struggling from couple of days to get my jdbc hive connection working using Zookeeper URI and after putting lot of effort finally I realised problem. In this post I will sharing my experience  and steps I took to rectify problem. Notes : I am having a HDP 2.6 sandbox along with my JDBC program . Use case : Many companies does not provide HiveServer2 url for configuring your JDBC string and its important because if your hiveserver goes down  , your whole job will abort (You will be missing Hive HA capabilities). So How do I dynamically determine second Hive Server URI ? Solution is to use Zookeeper Service Discovery feature. Zookeepers keeps all HiveServer 2 URI into its namespace. When client tries to make a connection to Hive , Zookeeper will look for available hive server and return URL to client program. You can quickly verify HiveServer namespace in zk Path with below command on HDP.  /usr/hdp/current/zookeeper-client/bin/zookeeper-client...
Read more

Access Kubernetes ConfigMap in Spring Boot Application

-
Image
 Hello There, Welcome back to our new post on Kubernetes tutorials. In this example we will see how can we configure and access ConfigMap in Spring boot application. ConfigMaps are helpful where you have multiple environment (Dev,Test Prod etc) and you want to promote your container with different environment configuration. There are three ways Pods can access ConfigMap in containers. For todays Demo , we will use Environment Variable approach. Pre-requisite : MiniKube Cluster   For Demo Purpose I have created Spring Boot application which will expose below end point.  curl localhost:8080/configMap Docker Image : shashivish123/springboot  Below is how Controller class looks like and value is being autowired from application.properties. Remember CONFIG_KEY value will be coming from Kubernetes ConfigMap Environment Configuration. Now Let's Begin , We will start by Creating firs ConfigMap in Kubernetes. Step 1: Create a namespace where we will ...
Read more

Developing Custom Processor in Apache Nifi

-
Image
Apache Nifi was developed to automate the flow of data between different systems. Apache NiFi is based on technology previously called “Niagara Files” that was in development and used at scale within the NSA for the last 8 years and was made available to the Apache Software Foundation through the NSA Technology Transfer Program. Nifi is based on FlowFiles which are heart of it. A FlowFile is a data record, which consists of a pointer to its content (payload) and attributes to support the content, that is associated with one or more provenance events. The attributes are key/value pairs that act as the metadata for the FlowFile, such as the FlowFile filename. The content is the actual data or the payload of the file. Provenance is a record of what’s happened to the FlowFile. Each one of these parts has its own repository (repo) for storage. Each flowfile is processed by FlowFile processor . Processors have access to attributes of a given FlowFile and its content stream. Processo...
Read more