Forem: Sai Laasya Vabilisetty

Explain to me like I am Five: Time Complexity

Sai Laasya Vabilisetty — Sun, 20 Sep 2020 08:36:32 +0000

Explain To Me Like I Am Five:

Time Complexity

Hello Everyone!!💛

Time Complexity is simply a measure of time it takes for a program to complete its task. Time complexity plays a crucial role in every spot while programming. So, let's try to simplify and learn now.

How to find time complexity?
Understanding asymptotic analysis
Analysis of Big-O complexities
Big-O cheatsheet
Do we consider time complexity of in-built functions?
Time complexity of conditional statements

How to find time complexity?

To check which algorithm is better for our task, one normal way is to run both algorithms on our computer and note which one is taking less time. But, this way of finding time complexity is not effective as results depend on the factors like the performance of the device, inputs given, etc. So, we check the time complexity using asymptotic analysis.

In Asymptotic Analysis, we evaluate the performance based on the input size we give. In other words, time complexity is estimated by counting the number of elementary steps performed by an algorithm to finish execution.
Let's see an example to understand this in a better way, let us try to find using two different cases.

1st Case

//psuedocode
int i = 1 to N
N = N + N
print N

2nd Case

//pseudocode
return N * N

In the first case, time will depend on N, as N increases time also increases. In the second case, any value of N we take we will get the result in one step(independent of N).

Understanding asymptotic analysis

Let's consider an example, there is a time complexity function obtained as T(n)=n^2+2n+8. Here for large values of n, (2n+8) becomes insignificant when compared to n^2.

We also neglect constant terms of higher-order coefficients. If we have 250n^2 and 300n^3, we only consider n^2 and n^3 ignoring constants.

Analysis of Big-O complexities

O(1)

Time complexity is said to be O(1) when it does not contain loop(which varies with input), recursion, or function call.

for(int i=0; i < 25; i++){
//statments
}

O(N)

Time complexity is said to be O(N) when the variables in a loop are incremented or decremented.

for(int i= n; i > 0; i--){
//statments
}

O(N^k)

Time complexity can be said O(N^k)(k can be 1,2,3...) by the number of times the innermost loop of the nested loop is executed.

for(int i= 0; i < n; i++){
for(j= 0 ;j < n; j++){
//statments
  }
}

O(logN)

Time complexity is considered as O(logN) if the loop variables are divided or multiplied by a constant.

for(int i = 0; i < n; i = i * c){
//statments
}

Big-O cheatsheet

Do we consider time complexity of in-built functions?

Yes, we do consider time complexity of in-built functions which effect time like Collections.sort() in java uses merge sort and has the complexity of O(NlogN), sort() in python which uses Timsort and has complexity as O(NlogN), etc.

Time Complexity of conditional statements

//pseudocode
input n
if n<7
print "n is less than 7"
else
for int i = 0 to n
print i

Here, observe the above code if the input we give is less than 7 then we execute only a print statement so time complexity is O(1). If the input is greater than 7 then there is a for loop which executes for n times. So complexity is n. Therefore best case time complexity is O(1) and worst case is O(N).

That's it. Now you can find time complexity of code by your own.😍

Scanner class nextLine() issue resolved in JAVA

Sai Laasya Vabilisetty — Fri, 18 Sep 2020 07:10:48 +0000

Hello everyone!😋

This article highlights the basic theme of the scanner and a common error while using nextLine() method. So why late, let's dive into the topic!🤿

What is the Scanner class?
Some basic methods in Scanner class
Why nextLine() method skips input?

What is Scanner class?

The scanner class belongs to java.util package. It is used for obtaining input for data types like int, char, double (all primitive types), string, used to read a file by passing file object. It can also be used for wrapper class objects.

We can access the methods of scanner class by a scanner object. While creating an object we pass System.in as a parameter. This tells the java compiler that the input will be provided through standard input (keyboard).

//creating a scanner object
Scanner scan=new Scanner(System.in);

Some basic methods in Scanner class

Some of the basic methods you need to know while using scanner class are

nextInt(): It scans the next token of the input as an int value.

 int a=scan.nextInt();

nextDouble(): It scans the next token of the input as double value.

double a=scan.nextDouble();

nextLine(): It scans from the current position until it finds a line seperator.

String s=scan.nextLine();

This will be explained more clearly in the next section. There are various other methods in Scanner class, you can check it here.

Why nextLine() method skips input?

So, to understand this clearly, let's start with an example.

public class ScannerExample {
    public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     System.out.println("Enter account number");
       int account_num=sc.nextInt();
     System.out.println("Enter account holder's name");
       String name=sc.nextLine();
     System.out.println("Enter the amount to deposit");
       double amount=sc.nextInt();
     System.out.print("Account number: "+account_num);
     System.out.print("Name: "+name);
     System.out.print("Amount: "+amount);
    }
}

Here, we are taking input for 3 variables account_num, name, amount using respective scanner methods, which we have learnt earlier. Let's check the output now.

Expected Output:

Account number: 154623
 Name: john doe
 Amount: 4000.0

Output we get:

Account number: 154623
 Name:
 Amount: 4000.0

Did you observe the difference?🤔The input we give using nextLine()for name is skipped and continued with the next one.

Why did this happen?

So, when we used nextInt() to get account_num it scans till the end of input 154623 and the cursor remains there after reading the number like this

154623👆   //cursor position after reading input

>Now, we know nextLine() is used to take a string as an input which there by accepts spaces too.

So, when we use nextLine(), it scans from where the cursor is and takes empty space as input. That's the reason why we got an empty line for name.

How to resolve this?

We can just use a nextLine() method right after taking int as input, so it takes the empty space away and allows us to give input for name. The code looks something like this:

  System.out.println("Enter account number");
     int account_num=sc.nextInt();
     sc.nextLine() //this takes away the empty space as input
  System.out.println("Enter account holder's name");
     String name=sc.nextLine();

We can also scan the complete line for integer using nextLine() and convert it to int using Integer.parseInt() , so nextLine() reads till end of line and parseInt() converts data into int.

System.out.println("Enter account number");
  int account_num=Integer.parseInt(sc.nextLine());
 System.out.println("Enter account holder's name");
       String name=sc.nextLine();

So, whenever you are using nextLine() after using any methods to get input like int, double, float etc, make sure that you apply these approaches.

If you are reading this line, you have reached the end of the article and you have learnt a new thing today.😍

Happy Java'ing!😊

Mastering 'this' keyword in Java.

Sai Laasya Vabilisetty — Tue, 01 Sep 2020 15:58:58 +0000

We mostly use this keyword as a reference to the current object in a method or a constructor. In simple words, it is a reference variable that points to the current object. In the below example, this keyword is used to refer to current class object.

class Example{
int a;
Example(int a){
this.a=a;           
}
public static void main(String args[]){
Example obj=new Example("John Doe");
}
}

But, there are many other cases where we can use this keyword efficiently. Let's explore them now.🤩

1. Using this keyword to eliminate confusion between class and instance variables.

If the variable declared in class and method/constructor share the same name then we use this keyword to refer class instance.

Explanation: As you can see in the below code, we have declared 2 global variables as place and pin, the same variable names are used for constructor parameters too. So, we use this to tell the program that the arguments we pass for the constructor variables are for the global variables too. Therefore, when we try to print pin and place in meth() it prints the values we passed during object creation.

public class Example{
    String place;
    int pin;
    One(String place,int pin){
     this.pin=pin;                  
    this.place=place;
    }
     void meth(){
      System.out.println(place+" "+pin);
    }
    public static void main(String args[]){
      Example obj=new Example("chennai",603103);                                          
       obj.meth();
    }
}

Output: chennai 603103

2. this keyword is used to call other constructors of the same class.

Here, we are using this to invoke a parameterized constructor inside a default constructor.

public class Example {
    Two(int a,int b){
    System.out.println("Parameterized Constructor");  
    }
    Two(){
        this(25,32);  
    System.out.println("Default Constructor");    
    }
    public static void main(String args[]){
    Example obj= new Example();   
    }
    }

Output:   Parameterized Constructor
          Default Constructor

3. Constructor Chaining

This is a process of calling one constructor from another constructor of the same class. The idea of this concept is already covered in the previous step, but let's explore it more clearly now.

Explanation:To understand clearly I have commented constructors with numbers in the below code. Now, when the object is created, constructor-1 is invoked which leads to constructor-2 as we used this() to call and thereby constructor-2 uses this() to call constructor-3. Therefore, the order of execution will be constructor 3,2 and 1.

public class Example {
 /*1*/ Example(){
        this(10,"laasya");
        System.out.println("Constructor 1");
        }
 /*2*/ Example(int a,String s){
        this(10);
        System.out.println("Constructor 2");
    }
/*3*/ Example(int a){
        System.out.println("Constructor 3");
    }
     public static void main(String args[]){
        new Example();
    }
}

Output: Constructor 3
        Constructor 2
        Constructor 1

4. Using this to invoke the current class method.

Explanation: Here we are using this to call one method from another. Instead of writing this.check() we can simply use check() which works completely fine. But it is recommended to use this as it ensures code readability in long run.

public class Example{
    void check(){
     System.out.println("This method is called from another method");
    }
    void checkTwo(){
        check();
    System.out.println("I called another method");      
    }
    public static void main(String args[]){
    Example obj=new Example();
    obj.checkTwo();
    }
}

output: This method is called from another method
        I called another method

5. Passing this keyword as a method argument

Explanation: In the below example, we have declared methodOne() which has a class object as a parameter. So, while calling methodOne() we can pass this as an argument which prints the value of 'a' which was passed to constructor during object creation.

public class Example {
int a;
Example(int b){
a=b;
}
void methodOne(Example object){
 System.out.println("I was called by using this keyword as arg "+a);
    }
void methodTwo(){
   methodOne(this);
    }
    public static void main(String args[]){
     Example obj= new Example(20);
     obj.methodTwo();
    }
}

Output: I was called by using this keyword as arg 20

6. Using this keyword to return the current class object.

Explanation: In the below code, when meth() method which is defined by class-name is called it returns the current class instance. Remember meth() returns but doesn't print. So, to print values we are using display().

public class Example {
   int age;
   Example(){
     age =20;
   }
    Example meth(){
        return this;
    }
    void display(){
       System.out.println(age);
    }
    public static void main(String args[]){
Example obj=new Example();
obj.meth().display();
    }
}

Output: 20

7. Using this keyword as a constructor argument

Explanation:In this below example, we have 2 classes A and T. When a new object of A is created, the default constructor of A creates a new object of class T passing this as an argument. Now, the default constructor of T stores the details of object A in object T as we did this.obj=obj. Hence, when we call `display()' it gets the value of the variable created in class A and prints it.

 public class A{
     int age=10;
     A(){
         T t=new T(this);
         t.display();
     }
     class T {
      A obj;
       T(A obj){
         this.obj=obj;
       }
       void display(){
           System.out.println(obj.age);
       }
   }
     public static void main(String args[]){
      new A();
    }

 }

Output: 10

That's it😍. You have reached the end of the article.
Happy Java'ing people🤗

Thank you for reading till the end. I would love to connect with you through Twitter, LinkedIn, Github.😍