0

Could I enquire, how do I check for the time complexity for the program below? (:

Thank you!

import javax.swing.*;
import java.awt.*;
import java.math.*;

/**
 *
 * @author Jia
 */
public class tilePanel extends JPanel
{
    int numSquares;
    int increment;
    private frame app;
    Integer buff;
    String x=" ";
    public tilePanel(frame app)
    {
        this.app=app;
    }
    public void paintComponent(Graphics g)
    {
        //super.paintComponent(g);
        g.setColor(Color.white);
        g.fillRect(0, 0, this.getWidth(), this.getHeight());
            if(app.p1.n1>0&&app.p1.n1<4)
            {
                g.setColor(Color.BLACK);
                numSquares  = (int)Math.pow(2, app.p1.n1);
                increment=(this.getWidth()-40)/numSquares;
                if(app.p1.x1>numSquares||app.p1.x1<1||
                        app.p1.y1>numSquares||app.p1.y1<1)
                {
                    app.activity.setText("Error!! Invalid value keyed!");
                }
                else
                {
                    for(int i=0;i<numSquares;i++)
                    {
                        buff=i+1;
                        g.drawString(buff.toString(), (increment*i)+22, 14);
                        g.drawRect((increment*i)+20, 15, increment, increment*numSquares);
                        g.drawString(buff.toString(), 5, (increment*i)+29);
                        g.drawRect(20, (increment*i)+15, increment*numSquares, increment);
                    }
                    g.setColor(Color.BLACK);
                    g.fillRect((increment*(app.p1.x1-1))+21, (increment*(app.p1.y1-1))+16,increment-1, increment-1);
                    g.setColor(Color.red);
                    Tile(app.p1.n1,app.p1.x1,app.p1.y1,increment,g,numSquares,x);
                }
            }
            else
            {
                if(app.p1.n1>=4)
                    app.activity.setText("Error!! The program only supports up to n=3");
            }
        
    }
    public void Tile(int n,int x,int y,int increment, Graphics g,int numSquares,String orientation)
    {
        int buf;
        int bufx=0;
        int bufy=0;
        int x2=0;
        int x3=0;
        int x4=0;
        int y2=0;
        int y3=0;
        int y4=0;
        buf=(int)((Math.pow(2, n))/2);
        
        if(n==1)
        {
            if(x%2==0&&y%2==0)
            {
                g.fillRect((increment*(x-2))+21, (increment*(y-2))+16, increment-1, (increment*2)-1);
                g.fillRect((increment*(x-2))+21, increment*(y-2)+16, (increment*2)-1, increment-1);
            }
            if(x%2==0&&y%2!=0)
            {
                g.fillRect((increment*(x-2))+21, (increment*(y-1))+16, increment-1, (increment*2)-1);
                g.fillRect((increment*(x-2))+21, increment*(y)+16, (increment*2)-1, increment-1);
            }
            if(x%2!=0&&y%2!=0)
            {
                g.fillRect((increment*(x))+21, (increment*(y-1))+16, increment-1, (increment*2)-1);
                g.fillRect((increment*(x-1))+21, increment*(y)+16, (increment*2)-1, increment-1);
            }
            if(x%2!=0&&y%2==0)
            {
                g.fillRect((increment*(x))+21, (increment*(y-2))+16, increment-1, (increment*2)-1);
                g.fillRect((increment*(x-1))+21, increment*(y-2)+16, (increment*2)-1, increment-1);
            }
            
            return;
        }
        if(orientation.compareTo(" ")==0)
        {
            bufx=buf;
            bufy=buf;
        }
        else if(orientation.compareTo("downleft") == 0)
        {
            bufx=buf;
            bufy=numSquares-buf;
        }
        else if(orientation.compareTo("downright")==0)
        {
            bufx=numSquares-buf;
            bufy=numSquares-buf;
        }
        else if(orientation.compareTo("upright")==0)
        {
            bufx=numSquares-buf;
            bufy=buf;
        }
        else if(orientation.compareTo("upleft")==0)
        {
            bufx=buf;
            bufy=buf;
        }
        
        if(x<=bufx&&y<=bufy)
        {
            orientation="upleft";
            g.fillRect((increment*(bufx))+21, (increment*(bufy-1))+16, increment-1, (increment*2)-1);
            g.fillRect((increment*(bufx-1))+21, increment*(bufy)+16, (increment*2)-1, increment-1);
            x2=bufx;y2=bufy+1;
            x3=bufx+1;y3=bufy+1;
            x4=bufx+1;y4=bufy;
        }
        else if(x <= bufx && y > bufy)
        {
            orientation="downleft";
            g.fillRect((increment*(bufx))+21, (increment*(bufy-1))+16, increment-1, (increment*2)-1);
            g.fillRect((increment*(bufx-1))+21, increment*(bufy-1)+16, (increment*2)-1, increment-1);
            x2=bufx+1;y2=bufy+1;
            x3=bufx+1;y3=bufy;
            x4=bufx;y4=bufy;
        }
        else if(x > bufx && y > bufy)
        {
            orientation="downright";
            g.fillRect((increment*(bufx-1))+21, (increment*(bufy-1))+16, increment-1, (increment*2)-1);
            g.fillRect((increment*(bufx-1))+21, increment*(bufy-1)+16, (increment*2)-1, increment-1);
            x2=bufx+1;y2=bufy;
            x3=bufx;y3=bufy;
            x4=bufx;y4=bufy+1;
        }
        else if(x > bufx && y <= bufy)
        {
            orientation="upright";
            g.fillRect((increment*(bufx-1))+21, (increment*(bufy-1))+16, increment-1, (increment*2)-1);
            g.fillRect((increment*(bufx-1))+21, increment*(bufy)+16, (increment*2)-1, increment-1);
            x2=bufx;y2=bufy;
            x3=bufx;y3=bufy+1;
            x4=bufx+1;y4=bufy+1;
        }
        Tile(n-1,x,y,increment,g,numSquares,orientation);
        orientation=checkOrientation(orientation);
        Tile(n-1,x2,y2,increment,g,numSquares,orientation);
        orientation=checkOrientation(orientation);
        Tile(n-1,x3,y3,increment,g,numSquares,orientation);
        orientation=checkOrientation(orientation);
        Tile(n-1,x4,y4,increment,g,numSquares,orientation);        
    }
    public String checkOrientation(String orientation)
    {
        if(orientation.compareTo("upright")==0)
            orientation="upleft";
        else if(orientation.compareTo("upleft")==0)
            orientation="downleft";
        else if(orientation.compareTo("downleft")==0)
            orientation="downright";
        else if(orientation.compareTo("downright")==0)
            orientation="upright";
        return orientation;
    }
}

Edited by Narue: Added code tags

4
Contributors
7
Replies
8
Views
6 Years
Discussion Span
Last Post by Rashakil Fol
0

Have you tested this program? It looks like your Tile method will keep running until your computer runs out of RAM.

0

it works. but only works correctly till n=3
anything bigger it'll give a wrong result.

0

Hmm, the majority of your complexity is in the Tile method because of the recursion. It looks like your return statement happens when n = 1, so if n > 1, you make 4 recursive calls to the Tile method. I would say the efficiency of just the Tile method is 4^(n-1). Because is n = 1 then return, but if n = 2 make 4 recursive calls "Tile(n-1,...)". This method can be mapped out like a tree but each node has 4 children. i.e

O            4^(n-1) where n = 1   return
  0 0 0 0         4^(n-1) where n = 2   4 total calls of the Tile method
0 0 0 0 0 0 0.... 4^(n-1) where n = 3  16 total calls of the Tile method

Thats my reasoning behind this efficiency. The rest of your program looks far more simple. By simple I mean linear, for loop O(n), the rest of it looks constant. I'm not sure about those errors yet. I hope this helps.

0

Thank you! Got another question relating to it.

The method that we are using will be the repeated (backward) substitution method by actually expanding the recurrence by substitution and then notice a pattern in it.

How do we use the result found which is a time complexity of [ 4^(n-1)]/ 3 to compute it to in big O notation?

0

I'm still a student myself, normally what we do in my classes is put it into an efficiency class, i.e. O(n^2) or O(n!). As the n value gets larger, the other stuff doesn't make much difference. Kind of like taking the limit as n goes to infinity. For this one algorithm, the main thing is 4^n, as n gets larger the -1 doesn't matter, and the /3 doesn't matter. So I would put this in the class of O(4^n). This is all I've done in my classes thus far. Maybe some others will be able to get you the rest of the way.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.