How to kill tomcat server?

This is the similar way to kill any responsive or unresponsive server/executable.

On MAC:

Step 1)

ps -awwef | grep tomcat

This gets the process identifier aka pid (3rd from the list when you run the command)

Step 2)

sudo kill -15 <pid>

Kills the given process

On WINDOWS:

Step 1)

netstat -o -n -a | findstr 8080

Step 2)

taskkill /F /PID 4184

 

UNIX/DOS Commands that I often use…

Command Description
sudo dscl . list /Users uid Lists all the users ids
sudo dscl . list groups gid Lists all the group ids
id -u
id -u RakeshChouhan
Gives the UID (user id) of username RakeshChouhan — Output is 502
dig rakeshchouhan.com Queries DNS and displays the given domain’s ip address in the terminal.
nl Gives the number of lines the file has.
export Used to Set Environmental variables
sudo Execute a command as another user
sudo -i OR sudo sh Log in as root
exit switch back to RakeshChouhan
ssh-keygen -R localhost Removes latest added ssh key and retains the old one.
ssh localhost Shows the last ssh login
ssh-keygen -t rsa -P “” Generates a SSH key (id_rsa.pub)
sudo chmod 700 /etc/ssh_host_dsa_key Changing permissions to ssh_host_dsa_key
cat $HOME/.ssh/id_rsa.pub >> $HOME/.ssh/authorized_keys copies the generated id_rsa.pub to authorized_keys in .ssh folder
cp copies a file from source and pastes in the destination folder.
ln -s Sets the link for the given fileName to the destination folder where the given
filename exists
ps aux | less Shows all current running process ids, with % of memory usage
ps Shows all current running process ids at current instance
ps -ef Shows all running process and as well monitor and refreshes the result in each
interval
lsof Shows all processes and PID’s
mkdir Creates a directory for the given name.
kill 12345 Kills the process id
jps Shows all current running Java Processes
man Shows the manual page that you want to see
echo $JAVA_HOME Shows the current mapped JAVA_HOME environment variable
echo $HADOOP_HOME Shows the current mapped HADOOP_HOME environmental variable
echo $PATH Shows the system PATH variable
clear clears the current working terminal screen
java -version Gives the java version
hadoop version Gives the Hadoop Version
pwd Shows the current working directory
exit Ends the Terminal’s process
find -f macos Finds the file named macos in the HardDisk
find . -type d | grep {directoryName}
OR
find / -name {directoryName} -type d
Finds the directory named {directoryName} in the HardDisk
rm -R -i Removes/Deletes each file and each sub directory from the given directory Name
with a prompt for each file and sub directory
rm -rf Removes/Deletes all files and sub directories without a prompt.
rmdir Deletes the given directory
ls Lists out the Non hidden files and directories in the current folder
ls -a Lists out all the hidden and non hidden files and directories in the current
folder
ls -l Lists out all non hidden files and folders alphabetically, and shows the file
and directory permissions,user,created date.
ls -help Lists out all the non hidden files and folders with more details (Users,
Groups, Access levels)
ls -l file.txt; echo $? Check if the file.txt is present or not in a particular directory.
wc Displays the Counts of lines, words, bytes in this order for the given
fileName
cd Change Directory
cd ~ Go to previous directory
du -sh | grep G Determines the Disk Usage in GB.
tar -xvfz Un-tars filename
vi Opens file with vi editor tool.
jar -cvf WAR_NAME.war * Creates a war for the given folder (Note that you should be in that folder for
that folder to be war)
grep ‘{WORD_TO_FIND}’ ‘{IN_FILE}’ Searches a text in the file. Ex: grep boo /etc/passwd. See grep for more
options.
grep {GREP_OPTIONS} ‘{WORD_TO_FIND}’ ‘{IN_FILE}’ Searches a text in the file. If using grep option

a). -A 10
Displays 10 more lines after (from the line where the text was found).
Ex: grep -A 10 boo /etc/passwd.

b). -B 10
Displays 10 more lines before (from the line where the text was found).
Ex: grep -B 10 boo /etc/passwd.

c). -C 10
Displays 10 more lines before and after (from the line where the text was found).
Ex: grep -C 10 boo /etc/passwd.

See grep for more options.

what is Gives What is What. What Does What ????
touch Creates a text file
cat > {fileName} Creates a fileName and opens it for edit/writing. “control + z” saves the file
and returns.
mv Moves a file from Source location and drops in destination location
rmr Removes the mentioned file from the destination location
ifconfig Gives the ip, mac addresses
netstat Gives the network status
netstat – a | grep “10123” Determines which remote hosts are connecting to your host on a particular port
say 10123
nslookup Determines your hostname and IP and viceversa
uptime Determines from how many days your server is up
stat Displays the fileName attributes/properties
sudo -s launchctl load -w /System/Library/LaunchDaemons/ftp.plist Loads FTP Server
sudo -s launchctl unload -w /System/Library/LaunchDaemons/ftp.plist UnLoads FTP Server
sudo apachectl start Starts MacOSX default Apache Server
sudo apachectl stop Stops MacOSX default Apache Server
sudo apachectl restart ReStarts MacOSX default Apache Server
httpd -v Gives the current Apache version
head -5

test.txt

Prints/Displays the first 5 lines of file test.txt
sed ‘5,$d’ test.txt Prints/Displays the first 4 lines of file test.txt — sed is the text editor
same as vi editor.
tail -5

test.txt

Prints/Displays the last 5 lines of file test.txt
sed -n ‘$p’ test.txt Prints/Displays the last 4 lines of file test.txt — sed is the text editor
same as vi editor.
head -5
test.txt | tail -1
Displays/Prints the 5th line from file test.txt
sed -n ‘4
p’ test
Displays/Prints the 5th line from file test.txt using sed editor
grep -c “Unix” Counts the number of times the word ‘Unix’ occurs in the given file
sed s/Unix/UNIX/g Replaces the word containing ‘Unix’ with ‘UNIX for the given filename
cut -f3 Gives only phone numbers, if my filename has tab separated Name, Address and
Phone numbers.
awk -f3 Gives only phone numbers, if my filename has tab separated Name, Address and
Phone numbers.
exit -1 Logout and Fail a Shell Script programatically.
chown Change file owner to the given userName of a given filePath
chgrp Change file groupName for the given fileName
sudo chattr +i/-i Change advanced file attributes.
/usr/sbin/system_profiler SPHardwareDataType | grep Memory Shows RAM memory (16GB)
df -h Determines how much space is left in current drive. Determines Configured SWAP
space. Swap files are created in (/private/var/vm) directory.
uname -p or arch Displays the processor type. (Current Processor architecture type is i386)
uname -a Displays the type of OS running on top of UNIX. (Here Darwin)
sw_vers Shows the Operating Systems version.
gcc -v Determines whether the required version of gcc is installed
ping or telnet Determines if a remote host is alive or not
top Determines which process is taking how much CPU
telnet hostname port Check if a particular process is listening on a particular port on remote
host.
sudo scutil –set HostName rakeshchouhan.com Sets the hostname (HostName is case sensitive)
hostname Gives you the hostname (case-sensitive). This is the same command in Windows. Also, you can “echo %COMPUTER_NAME%” in Windows to get the hostname.
sudo lsof -i -P | grep 8001 gives the process id of the application which is using port 8001 (PID is 3rd
from the left)
unzip -t file.zip Determines if a Zip file is corrupted.
unzip -j file.zip Unzips a Zip file.
echo “unix” | rev Reverses a string. From unix to xinu
echo “C for Cat” | rev | cut -f1 -d’ ‘ | rev Gets the last word from a line in Unix file. Explanation: The entire line is
reversed (taC rof C), then we cut the first word, we get (taC) and reverse it again.
sysctl -n machdep.cpu.brand_string Gives Processor information
ex: Intel(R) Core(TM) i7-3820QM CPU @ 2.70GHz
system_profiler Gives all the information related to PC (Camera, Bluetooth, Processor, Memory,
Wireless, etc..)
sytem_profiler SPHardwareDataType Gives Hardware Overview Informations.
sysctl -a | grep machdep.cpu Gives all CPU related information
find / -name .DS_Store -delete This deletes all .DS_Store files from all folders of MAC OSX file system.
curl -O
http://www.interior-dsgn.com/apache/maven/maven-3/3.1.1/source/apache-maven-3.1.1-src.tar.gz
Downloads apache-maven-3.1.1-src.tar.gz
sudo ln -s /Library/Java/JavaVirtualMachines/jdk1.7.0_45.jdk
/System/Library/Java/JavaVirtualMachines/1.6.0.jdk
Set a different Java Virtual Machine
sudo apachectl start Starts apache2 server (verify http://localhost)
sudo apachectl stop Stops apache2 server
brew update Use brew to install packages. This command updates brew formulae’s
brew install {packageName} Installs brew packages. Ex: brew install apache-spark
watch -n1 ls Watches the folder every one second. This is useful to keep a continuous watch on any folder, instead of typing ls -l on the folder every time. In order to watch for every 5 seconds for a given folder, use “watch -n5 ls”
Note that ‘watch’ command isn’t available implicitly. So we need to brew it before.
Ex: brew install watch
nc -l 8081 NetCat tool to allows clients to read from or write to network connections using certain protocols. In this case the client will be listening to port 8081.
Note: -l stands for listen
nc 127.0.0.1 8081 NetCat tool to allows clients to read from or write to network connections using certain protocols. In this case the client will be writing to 127.0.0.1 host at port 8081.

Jason Web Token (JWT)

What is a JWT?



It stands for JSON Web Token and it replaces the older cookie authentication and is now becoming the authentication standard.

  • Simpler & light weight.
  • Don’t have cookie authentication problems like setting Session states either in memory or database.
  • No database lookup to identify who the user is, as userId is embedded in the payload which is part of JWT’s.
  • No CORS issues as cookies are not being used.
  • Works with small and medium handheld devices (phones and iPads/tablets).

JasonWebToken


Life of a JWT

Every JWT has three parts. It begins with a header, in between is the payload, and at the end is the signature.

It all begins with the client trying to log in, where the HTTP request is send over with email and password to the backend, whether it’s for a login or just register. The backend will then validate the email and password and then 
it will encode the user ID and a few other things against the secret and something called a payload. Then our JWT, which is comprised of the header,
 payload, and signature, will be sent to the client. At this point, the client gets the JWT. It has no idea what’s inside. It doesn’t know what it is 
because it can’t decode it, only the server can, and so it just saves it inside its local storage and as long as it has that entry inside the local
 storage, it believes that it’s authenticated. Now let’s say the client restarts. The JWT is still in local storage because it’s persistent and because
 of that they’re still authenticated. No matter how many times the browser or client might restart, they’ll still be authenticated, unless,
 of course, the JWT expires.

JWT Payload Details:

JWTPayload


What if a client wants to request a restricted resource?



A restricted resource can only be accessed if you are authenticated. So to make that work, what we do is, 
we take our JWT from our local storage (on the front end web app) and embed it into an authentication header, which then gets passed back with any sort of request 
we make to our backend for our resource. That way our backend knows who we are from the payload since our user ID is in it and can authorize
us to have access to this resource.

H5 – Are you about to add an image to your Web Application ? Think about self encoded data-uri’s.

There are 2 ways to add an image to your html page.

1) Add it inline using your tag within html file
2) Add it using CSS

Everyone knows how to do it the both ways, but the best way to do is by using base64 encoder and adding the content data uri to the image.

I use a simply encoder utility tool from WebSemantics @ http://websemantics.co.uk/online_tools/image_to_data_uri_convertor/

The above utility tool does not allow images with large sizes, and here is another tool which does the same..

http://www.askapache.com/online-tools/base64-image-converter/

However, there are many tools that are available in the market. You can also have your own base64 algorithm to encode the images for security purposes (like avoiding “HOT LINKING“).

Given the input image, this tool gives you a base64 encoded data, which you would want to use it to attach it to html or css.

 

Amazing tiny tools I use {More to be Posted soon}

1). ngrok

This tool exposes your localhost to the outside world.

For Example: http://localhost:8080/webapps/amazeme/index.html is your application working locally. When you’d want to quickly demo it your PM/BA or someone else not over the firms/organizations VPN, then that’s where ngrok helps your application available to the outside world by tunneling thru your firewall.

Simply download ngrok script from ngrok.com specific to your OS. Using terminal/cmd promptI cd to the directory where it exists (I would recommend to move that script to the bin directory on MAC (if using Windows, set the environmental variables) to easily identify and work with ngrok) and then simply type in

ngrok http 8080

This now exposes (both secured and non secured urls) your localhost to the outside world using ngrok’s internal tunneling mechanism. You can learn more about it here.

So you can test your application  http://{alphaNumericTextFromTheTerminal}.ngrok.io/webapps/amazeme/index.html

2). tmi (too many images)

Discovers your images that needs improvement both on Mobile as well as Desktop.

npm install –global tmi

Installs tmi

tmi rakeshchouhan.com

Gives the Image Weight Summary both on Mobile and Desktop.

tmi rakeshchouhan.com –verbose

Gives detailed information of Images that needs to be Optimized. The list does not include the images which cannot be optimized further.

3). nslookup, ping (on Mac & windows), tracert, nbtstat (on Windows only).

nslookup rakeshchouhan.com

Gives the ip of the domain.

nslookup {ipFromAbove}

Gives information of the registered domain where rakeshchouhan.com was hosted.

4). tree

Get the dependency of each and every node_modules that has been installed (/usr/local/lib/node_modules).

Installing the tree:

There are several Package Managers available to install a package. The most used are below

brew install tree
sudo port install tree
fink install tree

Here you find the list of available package managers for each operating system

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

To know where the node modules are installed in your system

npm config list      // Check for cwd attribute

Then,

cd /usr/local/lib/                    // Change directory to the parent of node_modules
tree -d node_modules        // Gives the dependency on each installed node_modules

tree

 

Some Points about Abstract and Interfaces.

Abstract Classes:

1). A class defined as abstract cannot be instantiated. Meaning, you cannot call just/only new AbstractClass().You need to override all the methods that are marked as abstract as well.(See AbstractMain)

2). Abstract keyword is non access modifier.

3). When a method is marked as abstract, there should not be any implementation for the method.

4). Abstract methods have to be overridden in the sub classes.

5). Abstract classes NEED NOT have abstract methods. Those methods which do not have abstract defined, should be implemented. Meaning there should be a implementation code for this method right in this abstract class method body.

6). If there is atleast one abstract method defined in the whole class, then that class should be declared as abstract.

7). Classes and Methods marked as private cannot be abstract

8). Classes and Methods marked as static cannot be abstract.

9). Classes and Methods marked as final cannot be abstract.

10). Abstract classes can have default and as well as overloaded constructors. When no constructor is defined a default constructor will be generated by compiler.

11). Constructors of abstract classes are invoked when a subclass object is created. You can call the superclass constructor by calling super().

12). Abstract classes hides the functionality of those methods that are defined as abstract. The actual functionality of the abstract methods are exposed by the implementation classes.

13). Abstract Method Overloading signatures are supported in abstract classes.

14). By making this class as abstract and implementing the methods as well, will not give any compile time error., but gives a run time error after Instantiating the AbstractSubClass.

15).  @Override – Not necessary to provide this annotation, because, Compiler by default takes care of overriding, when it see’s extends keyword.

Interfaces:

1). Interfaces does not have any method implementation.

2). All methods in an interface are public and/or abstract.

3). Any field that is declared, is public and static.

4). There is no multiple inheritance in Java. Which means, any Java class cannot extend more than one class at a time. Instead there is a Multiple Interface Inheritance. Which means, any Java can implement/extends more than one interface.

5). Any Java class that implements any interface, will be having a ISA relationship, between the Java Class and the interface.

6). If a method deceleration in a interface is abstract, the whole interface need not be declared as abstract, this is unlike abstract classes.

7). Java does not support multiple inheritance, because of the Diamond of Death Problem.

8). Method Overriding is allowed in Interfaces. Each method signature in an interface is unique. Meaning, you can have multiple methods of same name with different arguments.

9). Multiple Interface Inheritance example can extend any number of interfaces.

Ex: public interface MultipleInterfaceImplementation extends InterfaceExample,AnotherInterface

* here InterfaceExample and AnotherInterface are both interfaces.

Source code: https://github.com/chouhan/CoreJavaBasics

Custom Module Loader in Flex

I know it’s too late to post this now, but I just found something which I created in October 2011, when I started cleaning up my hard disk.

package 
{

   import flash.display.DisplayObject;
   import flash.system.ApplicationDomain;
   import flash.utils.ByteArray;
   import flash.utils.Dictionary;
   import mx.controls.Alert;
   import mx.controls.ProgressBar;
   import mx.events.FlexEvent;
   import mx.events.ModuleEvent;
   import mx.modules.IModuleInfo;
   import mx.modules.Module;
   import mx.modules.ModuleLoader;
   import mx.modules.ModuleManager;
   import mx.utils.UIDUtil;

   public class CustomModuleLoader extends ModuleLoader{

        private var ichild:IModuleCommunication;
	private var loadRequested:Boolean = false;
	private var map:Dictionary = new Dictionary();
	private var module:IModuleInfo;
	private var progressBar:ProgressBar = null;
        private var _url:String = null;
        private var _dashBoardChildName:String;

	public function CustomModuleLoader(){
	    super();
	}
	
	public function get dashBoardChildName():String{
	    return _dashBoardChildName;
	}

        public function set dashBoardChildName(value:String):void{
	    _dashBoardChildName = value;
	}
	
	override public function get url():String{
	    return _url;
	}

        override public function set url(value:String):void{
	  if (value == _url){
	     return;
	   }
          if (module){
             unloadModule();
	     return;
	   }
          if (value == null || value == ""){
	     unloadModule();
	     return;
	   }
	_url = value;
	dispatchEvent(new FlexEvent(FlexEvent.URL_CHANGED));
	removeAllChildren();

	if (_url != null && _url != "" && loadRequested){
	   if (!map[_url]){
	      loadModule();
	    }
	    else{
	      child = map[_url];
	      addChild(child);
	     }
	   }
	}

        override public function createComponentsFromDescriptors(recurse:Boolean = true):void{
	   super.createComponentsFromDescriptors(recurse);
	   loadRequested = true;
	}

	override protected function measure():void{
	   super.measure();
	   trace("CustomModuleLoader Width--------------------------------------------- " + this.width);
	   trace("CustomModuleLoader Height--------------------------------------------- " + this.height);
	   this.percentWidth = 100;
	   this.percentHeight = 100;

	   if (progressBar){
	     progressBar.top = 200;
	     progressBar.left = 100;
	     progressBar.x = 200;
	     progressBar.y = 100;
	     progressBar.verticalCenter = 0;
	     trace("progressBar Width--------------------------------------------- " + progressBar.width);
	     trace("progressBar Height--------------------------------------------- " + progressBar.height);
	     trace("progressBar X--------------------------------------------- " + progressBar.x);
	     trace("progressBar Y--------------------------------------------- " + progressBar.y);
             trace("progressBar verticalCenter--------------------------------------------- " +  progressBar.verticalCenter);
             trace("progressBar horizontalCenter--------------------------------------------- " + progressBar.horizontalCenter);
	     trace("progressBar top--------------------------------------------- " + progressBar.top);
 	     trace("progressBar left--------------------------------------------- " + progressBar.left);
	   }
	}

	override public function loadModule(url:String = null, bytes:ByteArray = null):void{
	   if (url != null){
	      _url = url;
	     }
           if (_url == null){
	      return;
	    }
           if (map[_url]){
	      //trace("loadModule() - already created the child");
	      return;
	    }

	   if (module){
	      //trace("loadModule() - load already initiated");
	      return;
	    }
	   showProgressBar();
	   dispatchEvent(new FlexEvent(FlexEvent.LOADING));
	   module = mx.modules.ModuleManager.getModule(_url + '?cacheClear=' + UIDUtil.createUID());
	   module.addEventListener(ModuleEvent.PROGRESS, moduleProgressHandler);
	   module.addEventListener(ModuleEvent.SETUP, moduleSetupHandler);
	   module.addEventListener(ModuleEvent.READY, moduleReadyHandler);
	   module.addEventListener(ModuleEvent.ERROR, moduleErrorHandler);
	   module.addEventListener(ModuleEvent.UNLOAD, moduleUnloadHandler);
	   module.load(ApplicationDomain.currentDomain, null, bytes);
	}

        override public function unloadModule():void{
	  if (map[_url]){
	     delete map[_url];
 	  }
          if (child && contains(child)){
	     ichild.handleDispose();
	     removeChild(child);
	     child = null;
	     ichild = null;
	     _url = null;
	   }
          if (module){
	     module.removeEventListener(ModuleEvent.PROGRESS, moduleProgressHandler);
	     module.removeEventListener(ModuleEvent.SETUP, moduleSetupHandler);
	     module.removeEventListener(ModuleEvent.READY, moduleReadyHandler);
	     module.removeEventListener(ModuleEvent.ERROR, moduleErrorHandler);
	     module.removeEventListener(ModuleEvent.UNLOAD, moduleUnloadHandler);
	     module.release();
	     module.unload();
	     module = null;
	  }
	     applicationDomain = null;
	     removeProgressBar();
	 }

	private function moduleErrorHandler(event:ModuleEvent):void{
	    removeProgressBar();
	    dispatchEvent(event);
	}

	private function moduleProgressHandler(event:ModuleEvent):void{
	    dispatchEvent(event);
	}

	private function moduleReadyHandler(event:ModuleEvent):DisplayObject{
	    removeProgressBar();
            child = module.factory.create() as DisplayObject;
            ichild = child as IModuleCommunication;
            ichild.setModuleParent(this.parentApplication);

	    if (url == "DashboardModule.swf"){
	      ichild.setDashboardChild(dashBoardChildName);
	    }
 	   dispatchEvent(event);
           if (child){
		addChild(child);
		map[url] = child;
	    }
	   return child;
	}

	private function moduleSetupHandler(event:ModuleEvent):void{
	    dispatchEvent(event);
	}

	private function moduleUnloadHandler(event:ModuleEvent):void{
	    removeProgressBar();
	    dispatchEvent(event);
	}

	private function removeProgressBar():void{
	    if (progressBar)
	    {
		removeChild(progressBar);
	        progressBar = null;
	    }
	}

	private function showProgressBar():void{
	 if (!progressBar)
	  {
	    progressBar = new ProgressBar();
	    progressBar.labelPlacement = "top";
	    progressBar.source = module;
	    progressBar.verticalCenter = 0;
	    progressBar.indeterminate = true;
	    addChild(progressBar);
	}
     }
  }
}

Big O, Omega and Theta Notations.

Big O, Omega and Theta Notations are used to describe not only the way an algorithm performs but the way an algorithm scales to produce a output. It measures the efficiency of an algorithm with respect to time it takes for an algorithm to run as a function of a given input. They are used to determine the Worst case complexity, Best case complexity and the Average case complexity.

Big Omega notation describes the best case of a running algorithm. In contrast, Big O notation describes the worst case of a running algorithm.

Big O Notation is denoted as O(n)  also termed as Order of n, or also termed as O of n.

Big Omega Notation is denoted as Ω(n) also termed as Omega of n.

Apart from Big O (O) and Big Omega (Ω), there are Big Theta (Θ), Small O (o) and Small Omega (ω) notations that are used in computer science programming. You can get more information from http://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation.

O(1) – Constant Time

This means that the algorithm requires the same fixed number of steps regardless of the size of the task.

Examples:

1). Finding an element in a HashMap is usually a constant time, which is O(1). This is a constant time because, a hashing function is used to find an element, and computing a hash value does not depend on the number of elements in the HashMap.

2). Push and Pop operations for a stack containing n elements.

3). Insert and Remove the operations of a queue.

O(log n) – Logarithmic Time

This means that the algorithm requires the Logarithmic amount of time to perform the task.

Examples:

1). Binary search in a sorted list or Array list of n elements.

2). Insert and Find operations for a binary search tree with n nodes.

3). Insert and Remove operations for a heap with n nodes.

4). Fast insertion, removal and lookup time of a TreeMap (a.k.a balanced tree because a TreeMap maintains key/value objects in a sorted order by using a red black tree) is O(log n)

O(n) – Linear Time

This means that the algorithm requires a number of steps directly proportional to the size of the task.

Examples:

1). Traversal or searching of a list(a linked list or a array) with n elements. This is linear because you will have to search the entire list. This means that if a list is twice as big, searching will take twice as long.

2). Finding the maximum or minimum element in a list, or sequential search in an unsorted list of n elements.

3). Traversal of a tree with n nodes.

4). Calculating iteratively n-factorial, for example finding iteratively the nth Fibonacci number.

O(n log n) – N times Logarithmic time

This means that the algorithm requires N times the Logarithmic time of solving a algorithm.

Examples:

1).  Advanced Sorting Algorithms like quick sort and merge sort.

O(n2) – Quadratic Time

Examples:

1). Simple sorting algorithms, for example a selection sort of n elements.

2). Comparing 2 two dimensional arrays of size n by n.

3). Finding duplicates in an unsorted list of n elements.

Note: If a solution to a problem has one single iteration, in other words, if the solution is achieved by either only one for loop or one while loop or one do-while loop or a single recursive function, then that algorithm is said to perform with O(n) else if the solution is achieved by 2 nested loops, then the algorithm is said to perform with O(n2) and if it is achieved by 3 nested loops, then the algorithm is said to perform with O(n3) and so on..

O(n3) – Polynomial Time

Examples:

1). Given a expression 23n3 + 12n2 + 9, and n = large numbers, the execution time for n3 increases drastically which takes O(n3) to perform the operation.

O(an) for a > 1 – Exponential Time

Examples:

1). Recursive Fibonacci implementation

2). Problem to solve Towers of Hanoi

3). Generating all permutations of n symbols.

Here is the order of execution time, in which the way Big O notations worst case behavior is determined.

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) <O(an)

Constant Time < Logarithmic Time < Linear Time < N times of Logarithmic Time < Quadratic Time < Polynomial Time < Exponential Time.

If algorithm is __ then its performance is __

algorithm performance
o(n) < n
O(n) ≤ n
Θ(n) = n
Ω(n) ≥ n
ω(n) > n
4 important Big O rules:

1). If you have 2 different steps in your algorithm, add up those steps

Example:

function something() {
    doStep1();	// O(a)
    doStep2();	// O(b)
}

Overall runtime: O(a+b)

2). Drop Constants

function minMax1(array) {
	min, max = null
	for each e in array
		min = MIN(e, min)	//O(n)
	for each e in array
		max = MAX(e, max)	//O(n)
}

Another example:

function minMax2(array){
	min, max = null
	for each e in array
		min = MIN(e, min)
		max = MAX(e, max)	
}

Overall runtime: O(2n)
So dropping the constants overall runtime equals to O(n)

3). Different Arrays is equivalent to (=>) Different Variables.

function getSize(arrayA, arrayB){
	int count = 0;
	for a in arrayA{
		for b in arrayB{
			if(a == b){
				count = count++;
			}
		}
	}
	return count;
}

Overall runtime is NOT O(n^2), but instead it is O(a * b)

Note that, the loops are emulated on 2 different array’s.

4). Drop non dominant terms.

function printSize(array){
	max = null;
	
	// runtime for the below loop is O(n)
	for each a in array{
		max = MAX(a, max);
	}
	
	//runtime for the below nested loop is O(n^2)
	for a in array{
		for b in array{
			print a, b;
		}
	}
}

Overall runtime: O(n + n^2)

However, since O(n) is too small and can be neglected.
In other words,

O(n^2) <= O(n + n^2) <= O(n^2 + n^2)
O(n^2) <= O(n + n^2) <= O(2 * n^2)

Now, dropping the constants based on Rule 2,

O(n^2) <= O(n + n^2) <= O(n^2)

if left and right are equivalent, then center is too..

i.e O(n + n^2) is equivalent to O(n^2)

Hence, overall runtime is O(n^2)


Sources:

Click to access BIG-O.pdf


http://bigocheatsheet.com/

This post was more or less taken from the afore mentioned sites, with little or more changes based on my knowledge and observation. I will be adding more examples to one or more above mentioned time analysis Big O notations as and when I come across in the near future of programming career.

Multiplication Table..

package solutions.java;

/**
 * Created by rchouhan on 11/1/14.
 *
 * For Zero iterations
 * O(N) < Olog(N)
 *
 * replace N with 0; and log(0) = 1
 *
 * For N > 0
 *
 * O(N) < Olog(N) < O(Nlog(N)) < O(N + N) (also O(2N)) (or also O(N^2)) < O(N^N)
 */


public class MultiplicationTable {

    public static void main(String[] args){
        multiplicationTable(3);
        multiplicationTableUntil(3);
    }

    // Time Complexity is O(N)
    static void multiplicationTable(int i){

        for(int j=0; j<=10; j++){
            System.out.println(i +" X " + j +" = " + i*j);
        }
    }

    // Time Complexity is O(N^2)
    static void multiplicationTableUntil(int input){
        for(int i=1; i<= input; i++){
            System.out.println("\nMultiplication Table for " + i + "\n");
            for(int j=0; j<=10; j++){
                System.out.println(i +" X " + j +" = " + i*j);
            }
         }
    }
}

Odd’s and Even’s using..

Write a method to print all odd and even numbers of a given number.

Again this can done using

for loop and
recursions

package solutions.java;

/**
 * Created by rchouhan on 10/30/14.
 */
public class OddAndEvenNumbers {

    public static void main(String[] args){
        System.out.println("\nPrinting all odd numbers for the given input using for loop: "+ getOddSequenceUsingFor(100));
        System.out.println("\nPrinting all even numbers for the given input using for loop: "+ getEvenSequenceUsingFor(100));
        System.out.println("\nPrinting all odd numbers for the given input using recursion: "+ getOddSequenceUsingRecursion(100));
        System.out.println("\nPrinting all even numbers for the given input using recursion: "+ getEvenSequenceUsingRecursion(100));
    }

    // Using FOR loop

    // Time Complexity is O(n) - linear
    private static String getOddSequenceUsingFor(int input){
        String oddValues = "";
        for(int i=1; i<= input; i +=2){
            oddValues += i + ",";
        }
        return oddValues;
    }

    // Time Complexity is O(n) - linear
    private static String getEvenSequenceUsingFor(int input){
        String evenValues = "";
        for(int i=0; i<= input; i +=2){
            evenValues += i + ",";
        }
        return evenValues;
    }


    // Using Recursion

    // Time Complexity is O(n) - linear
    private static String oddValues = "";
    private static int i =1;
    private static String getOddSequenceUsingRecursion(int input){
        if(input < i){
            return oddValues;
        }
        oddValues += i + ",";
        i +=2;

        return getOddSequenceUsingRecursion(input);
    }

    // Time Complexity is O(n) - linear
    private static String evenValues = "";
    private static int e =0;
    private static String getEvenSequenceUsingRecursion(int input){
        if(input < e){
            return evenValues;
        }
        evenValues += e + ",";
        e +=2;

        return getEvenSequenceUsingRecursion(input);
    }
}