/dpt/ - Daily Programming Thread

What are you working on, Sup Forums?

Old thread:

Dumb shitposting general

Let the idea that an n*n matrix is linear continue

>What are you working on, Sup Forums?
>working on
>working

second for all algorithms run in linear time confirmed for new meme

How do you make a videogame?

>bumping for digits
Also, i'm currently learning how to get started in programming
unfortunately for me, i'm just stuck without having a single clue where to start

step 1) become a loser

Done!

import math;

x = 0;

x = x + 1;

while x > 0
if x == 1
print "Hello world";

this is my first program

It doesn't run

I'm learning p5js and trying to make myself a cool personal website with HTML5 and scripting languages

the internship search is to no avail pls help lads

did you used the notepad?

The real meme is that all nested loops are polynomial

Learn C++
Learn some graphics API/library
Learn some high school math and physics
???

HOW DO YOU MAKE SQUARE MATRICES FROM NON-SQUARE MATRICES, THE GUIDE

1. Measure the dimensions of your numbers. Let's say, they are A and B.
2. Solve the equation, Ax = By
The solution to the equation make the number of elements by each dimension.

Example: here's a bunch of non-square numbers, each has 3*2 measurements.
Solving the equation 3x = 2y, we get x = 2, y = 3.
Thus our matrix is going to be square.
Let's see it:
+-+
+-1

It's one of our non-square numbers.

+-++-+
+-1+-2
+-++-+
+-3+-4
+-++-+
+-5+-6

Look! Our non-square numbers made square matrix!

How often do you take your work home with you?

def f(n):
for i in range(n):
for j in range(n):
pass #basic operation

are you really unironically saying this is a function with linear time complexity?

>/dpt/ is full of undergrads who failed their first algorithms course
Wow, what's new?

No, SOME loops are polynomial. ALL != SOME

Sometimes, then I just finish whatever I needed to finish to be done for the day, call in the next day that I'm working from home today, spend my day on whatever I wanted to spend it without thinking about job and submit the changes at the end of that day that I actually made yesterday.

def f(n):
for i in range(n*n):
pass #basic operation

Ok so just making sure, this has the same complexity as above, correct?

def f(n):
for i in range(n):
for j in range(5):
pass #basic operation

Notice that there is a nested loop and it isn't O(n^2).

import math;

x = 0;

flag = false;

x = x + 1;

if x == 1
flag = true;

while x > 0
if flag == true;
print "hello world";

i used excel

Classes are obsolete when you have heterogeneous lists and tagged types.

No

>call in the next day that I'm working from home today,
That sounds nice, what is your job?

Contrary to popular belief, determining time complexity is NOT as simple as counting the for loops.

Yes

This

That's not a function of a nested loop, technically, since it can be unrolled.

Just a programmer in a small Python workshop.

Oh, so
for i in range(sqrt(n)):
for j in range(sqrt(n)):


is not a nested loop either?

Tell me the time complexity here
void fun(int n) {
for (int i = 0; i < n; i *= 2)
for (int j = 0; j < n; j++)
basic_operation();
}

O(inf) or however you'd write it

That one can be unrolled too, because again it's linear. What are you missing?

O(nlog2(n))

this can be unrolled to
for i in range(sqrt(n)*sqrt(n)): stuff
which will run sqrt(n)*sqrt(n) = n times
it is O(n)

n^2

Can you guys not math?

Look again

Oops, i = 1

THE POINT IS THAT counting for loops is fucking stupid, trying to determine what can and can't be unrolled is fucking stupid, what's easier is just creating a mathematical formula for the number of operations and then reducing this to O notation, like you're fucking supposed to do.

e.g., for nested loops with bounds only depending on 'n', you could find the complexity by multiplying the bounds. For two loops to 'n', it would be n*n = n^2. For a loop to 'n' and a loop to 5, it would be n*5 = O(n)
It's fucking simple.
I hate this website

>Anonymous 03/11/17(Sat)20:26:14 No.59352080 ▶
>
>Tell me the time complexity here
>void fun(int n) {
> for (int i = 0; i < n; i *= 2)
> for (int j = 0; j < n; j++)
> basic_operation();
>}
>>>
> Anonymous 03/11/17(Sat)20:27:03 No.59352094 ▶
>
>O(inf) or however you'd write it
>>>
> Anonymous 03/11/17(Sat)20:27:13 No.59352099 ▶
> (You)
>That one can be unrolled too, because again it's linear. What are you missing?
So tell me, what complexity does printing every element of a matrix exactly ONE time have?

1/2 n * n = 1/2n^2 = n^2

You've never taken a class on this have you?

It's not 1/2 n, it's log2(n), since i multiples itself by 2 each time, not increment of half of n.

n*m if we're referring to matrix dimension, n if we're referring to number of elements

>So tell me, what complexity does printing every element of a matrix exactly ONE time have?
n*m, where n and m represent the number of rows and columns of the matrix, respectively.

For a 2d matrix?

O(n*m) where n and m are the dimensions of the matrix

Yeah fuckwit, the outermost loop completes in 1/2 n operations. Where the FUCK do you think it's exponential?
>autists in charge of FUCKING MULTIPLICATION

The problem says i *= 2, NOT i += 2.

Please be a troll, for the sake of humanity

nvm, I can't read

then it'd be nlogn yeah
>actually specifying the 2
You know that's not how it works right

So in other words, LINEAR COMPLEXITY. Thank you very much.

This.

A better way to say it would be that any nested loop that iterates over the same range is going to be n^2.

Literally nobody has ever made an algorithm where you need to do i * 2. The code was obfuscated intentionally, like the pigeon that plays Chess.

for n 20, you don't get 2 4 6 8 10 12 14 16 18, you actually get 1 2 4 8 16

Or, to find the complexity of nested loops with bounds that don't depend on the iteration variables, multiply the bounds of each loop?

...

you were trolling pretty will til then, it was a good run though

No. Specifying elements discards information of a matrix. n*m describes the matrix. Not one person would honestly say matrices are defined by their number of elements.

HAHAHA HE CANT ACTUALLY READ

How the fuck is iterating every element ONCE and ONLY ONCE and performing the basic operation ONCE and ONLY ONCE per element not linear you dumb fuck?

Holy shit have you ever taken a simple course in CS?
I can think of a few algorithms with logarithmic time, two of which specifically does multiply instead of increment the iteration variable

>shitting up two threads because some autismo couldn't be asked to define n and instead posts algorithms without context

I work from home

It's linear in the number of elements, which is m*n.

A function of two arguments cannot be described as just "linear"; it can be described as linear in one or the other arguments, but not "linear in general"
This board fucking sucks at math

What is a code of conduct and why does my project need one?

Because if the number of elements isnt the *size*, the *size* is the input of the function

if the function is defined

def f(n):
for i in range(n*n):
pass #basic operation

the input is *n*, the number of elements/number of times the operaiton is performed is n^2

You can't define a unique matrix by it's number of elements. Trying to create a matrix of 4 elements has infinite possible solutions. You know define has mathematical meaning right?

>Trying to create a matrix of 4 elements has infinite possible solutions.
1*4
2*2
4*1

>he thinks there are only 2d matricies

Are you unable to read? Big O refers to the TIME COMPLEXITY, not the fucking number of elements. The TIME COMPLEXITY of printing every element ONCE is linear, aka O(n)

Nobody gives a fuck about the size of the matrix you dumb fucks.

The input to f is clearly the matrix. The basic operation is printing an element. Are you retarded or just pretending to be?

Good point.

I said by 2, not by anything you moron. Bubblesort doesn't multiply anything by 2, try again.

>Sup Forums thinks printing elements in an N*M matrix is polynomial

What is n?

Haha. LOOK AT HIS SHITTY BAIT AND LAUGH

Why are there so many raging people ITT, calm down folks.

Time complexity is a function of the size of the inputs. For a matrix, there are two input sizes, 'n' and 'm', and the time complexity is a function of both of those variables.
Specifically we could say T(n,m) = a*n*m + b*n where n and m are the number of rows and columns of the matrix, a is the time it takes to print an element, and b is the time it takes to print a newline.
O notation reduces this to O(n*m)

>get told
>"i-i-i was only pretending you guise"

This

This. I don't know where the fuck "defining a matrix" came from.

Number of elements. In the 2D matrix example, it's N*M.

n is a function of two variable raised to the first power. That makes it a polynomial function

So it's linear in the number of elements, which is n*m. If there's more than one variable, you can't simply say "linear time" because you have to indicate which variable you mean. With one variable, it's implicit.

int fast_exponent (int b, int n) {
int x = 1;
for (int i = 1; i

>Time complexity is a function of the size of the inputs
And what is the input to the algorithm that prints every element of an NxN matrix? Is it not the fucking NxN matrix?

> For a matrix, there are two input sizes, 'n' and 'm', and the time complexity is a function of both of those variables.
The input sizes defines the matrix, not the algorithm. Anyway, by definition, O(n * m) must in this case be linear time, since the basic operation is only performed once for any element.

Instead of thinking it by *= 2, think of it as

What time complexity does printing every element in a matrix one time have?

Protip: It's not fucking polynomial

See above

I never touch code at home but I'll answer an occasional question

What's a good book for me to better understand time complexity?

def ZeroMatrix(n,m): #this prints a 2D n by m zero matrix
for _i in range(m):
for _j in range(n):
sys.stdout.write("0 ")
sys.stdout.write("\n")

The "inputs" ie "size" of this function are n and m
The "basic operation" of this function is
sys.stdout.write("0 ")

The basic operation runs n*m times
The time complexity is O(n*m)

It is funny that there are people here who would disagree with any of this

For an nxm matrix, would a function in O(n) be linear as well?
For an nxn matrix would a function in O(n) be linear?

This question doesn't really make sense,
Any function in O(n) is

Wikipedia probably has everything you need. After looking at algorithms in each common ranges of complexity, you'll get the hang of it.

Yeah, people in this thread are also fucking retarded for thinking that m in the context of Big O can be used for defining the number of items in a matrix as n * m. The total number of elements in a matrix is just described as n in Big O, because it's the amount of data being operated on. m is another variable amount of data that grows with time, but for the sake of big O they're treated as the same variable.

For example, with bubble sort, you can easily write the algorithm to iterate one less time in the inner loop for each pass of the outer loop, so you're on a list, n, and n -1, or m, making the time complexity n*m, or for each item of n you have to iterate m times. However, in Big O this is still just described as n^2 because it's going to grow faster than something that is O(n).

This whole array nonsense is fucking retarded. Yes, a square matrix will obviously be the number of rows or columns squared, but that has nothing to do Big O, unless creating the matrix is part of the algorithm being analyzed. Talking about a matrix AFTER it's created, the number of items in terms of Big O is just n, and analyzed accordingly.

What you niggas need to understand is that the n in O(n) doesn't refer to a side in the matrix, it refers to every access the algorithm does to the matrix.

A matrix can only be defined in a single variable for one subset of matrices, a trivial set we don't even call matrices. If you are attempting to define all matrices in a single variable then you are not just wrong, but incorrect, by definition. If you're going to be Autistic at least be correct.

I guess I'm saying that linear is a bad way to describe algorithms on non-linear objects

>every function is linear because once the numbers are filled in you only perform operations once
How can you be THIS DUMB

I want to pick up an old computer to start tinkering with BASIC coding the way it used to be. Would you recommend a ZX Spectrum, C64 or an Amiga?

In terms of Big O analysis, it's just the number of elements in a data structure, or n.

Nice weasel words, but you're dodging the fucking question. What time complexity do you think printing every element in an array (2D, 3D, ..., nD) have?

If you answered "linear" to that, then the Big Oh notation for this is O(n) where n refers to the number of elements, not the fucking matrix dimensions.

Invariant: If you answered anything other than linear to that question, you're a fucking retard and need to take an introductory class on algorithms.

Start programming shit
Thats how you start

none. you can run a BASIC environment on your current computer. don't fall for the nostalgia of people who never had to code on these old, slow machines.