Hi, still new to algorithm analysis and need some help confirming my answer or not.

I assumed that best case would be O(1) in this scenario if size of the array is either 0 or 1. But trying to review my answer with online resources, it say's that O(1) doesn't count here?

What is the definite answer here?

EDIT: Hey everyone! Glad everyone got to interact and give responses. The answer was O(N) in the end! Confirmed with my professor.

If someone asks for big O time complexity of an algorithm but expects only the minimum of the possible big Os then is that even Big O notation anymore? cuz if the big o time complexity of an o(n) algorithm is asked then according to the condition of big O notation O(n square) would also be a valid answer

I'm not asking someone to write an essay but I'm not that dumb either.

I look at basic coding for html and python and I'm like, ok so you can move stuff around ur computer... and then I look at a video game and go "how did they code that."

It's not processing in my head how you can code a startup, a main menu, graphics, pictures, actions, input. Especially without needing 8 million lines of code.

TLDR: HOW DO LETTERS MAKE A VIDEO GAME. HOW CAN YOU CREATE A COMPLETE GAME FROM SCRATCH STARTING WITH A SINGLE LINE OF CODE?????

Im just a dumb dumb stinky little mechanical engineer. And i wanted to see if a mechanical computer is even possible. Like what part exactly would i need for a simple display, because the most i know is logic gates and ROM. I made mechanical logic gates (kida, just or and not. Still cleaning up and) and an idea of a ROM system(i think rom is the memory one). So like what else would i need to build a computer besides memory and imputs??

And on a side note how long should my binary be?? Im useing 8 nodes to store one input so i can use the alphabet, numbers, special characters, colors, and some free spaces to use for other functions. Did I go overkill with 8?? I needed 6 for alphabet and then i added to 7 to use numbers and put 8 just in case i needed more.

This is my sos call for all actually smart ppl out here

(Edit): THANK YOU ALL FOR THE FEEDBACK T-T. This was just a little question I had because it sounded K O O L but there’s a few of you all who actually seem to see how this goes so I’m going to make updates on yt for now on :D

If I ask that on Google, it returns 16 or 24-bit. To make this shorter, 8 bits would 00000000. You have that range to use zeros and ones to convey information. So, here's my question, a single sequence of 24 numbers can convey how much of a song? How many sequences of 24 bits does a typical 4min song have?

This is from John Maedas book and hes trying to explain how to think more exponentially. Hes talking about taking a 10mm line and then projecting to 2d and it occupies 100 square mm of space, but then for a cube wouldnt it be 1000 cubic mm not 10,000. Was he confusing this for the example of when you expand the length of the side the space expands exponentially with the amount of dimensions? Overall just confused and wondering if I missed something.

Well, I don't know if I'm the only one who suffers from this or not. I've studied a lot of subjects of computer science and programming, .... more thing, and when I go back to something I've studied before—whether it's a concept, a mechanism, or anything else—I find I've forgotten it. I really hate having to revisit what I've already learned, and I can't accept having to revisit it every time so I don't forget it. There are really so many things, and I also want to focus solely on learning new things. I would be happy to read your solutions

I am 18 and will start CS at Uni this September. I’ve started learning C# with Alison.com and have made notes on paper when working through the videos to build my understanding. Am I doing it correctly? I want to learn the concepts before going knee deep into starting my own projects.

This question is from 4.24 of the book Data Structures by Seymour Lipschutz. I can't wrap my head around it, especially the part where we add E2 to E1L2 or where we add E3 in the last step. Kindly explain it for me.

If you personally know or have the link for a course that explains it in detail, i would appreciate that

I know I can't just directly cancel nlogn with theta(nlogn).

Can anyone please help to solve this 🙏

As a computer scientist, some of the questions asked on this subreddit are genuinely depressing. Computer science is such a vast topic - full of interesting theories and technologies; language theory, automata, complexity, P & NP, AI, cryptography, computer vision, etc.

90 percent of questions asked on this subreddit relate to "which programming language should I learn/use" and "is this laptop good enough for computer science".

If you have or are thinking about asking one of the above two questions, can you explain to me why you believe that this has anything to do with computer science?

Edit: Read the comments! Some very smart, insightful people contributing to this divisive topic like u/kedde1x and u/mathsndrugs.

I've always been curious and no matter how many videos I watch, they all end with that at the very basic level computers do arithmetic operations and work with memory address. But, how does that all translate into these videos, games, software, mouse clicks, files, folders, audio, images, games, animation, all this UI, websites and everything.

If all it's doing is arithmetic operations and working with addresses then how does this all work and what makes it possible. I know that I might sound very stupid to a lot of you, but if I can get any resources to figure this out, I'll be grateful.

I know it'll take a lot of time, but I'm ready to take it on.

What exactly is the difference between these two, they seem very similar at first glance?

Thank you.

While reading Michael Sipser's book on Theory of Computation, i have found the following problem

"2.22: Let C = {x#y | x, y belong in {0,1}* and x != y}. Show that C is a context-free language. "

I have been trying for many hours to find a proof for this, but i cannot.
I cant find a way to use a PDA, since when comparing X with Y i am going to be comparing the one on the stack backwards and Any attempt at a grammar has failed. After a couple web searches i only found that this is conisdered a cfl but not its grammar or some other proof.

Edit: The closest i have gotten to:
S->A#B | B#A
A-> TAT | 0
B-> TBT|1
T-> 1|0

but it doesnt work for strings with 2 characters (cant generate something like 10#11). If i allow T to make an empty string or split TxT into Tx and xT then it can create strings x=y.

Edit: I havent been able to find a grammar for this but as u/hanshuttel said you CAN do it with a pda.
Since you dont need to save the entirety of X, but only 1 character and it's index, you can just "save" the character by splitting into 2 paths, one where you compare Y's character with Xi=0 and one where you compare it with Xi=1. Then use the stack to save Xi's index and nondet. compare all X's.
This, combined with the simple pda that checks |x|!=|y| will get the PDA for C.

Technically I could convert this into a grammar thats super tedius and the grammar will be really convoluted so i dont think theres any value to that.

I genuienly still have no clue how to deal with even length x and y without allowing x=y cases in a grammar not a single think i tried led anywhere.

What are the basic computer skills? Anything related to computer software and hardware.

I know that computers understand binary, and thats how everything is done, but how do computers know that 01100001 is "a", and that 01000001 is "A"? I've never heard or seen an explanation as to HOW computers understand binary, only the fact that they do–being stated as an explanation to why they understand it.

Hello all, sorry if this question is a little ridiculous; please let me know if I am posting in the wrong place.

For context, I am a self-taught developer with more of a humanities background, but I have been passively (and recently more actively) interested in CS for most of my life (specifically in computer graphics) and I am trying to understand the "abstraction gap" in CS. Essentially, I hope to understand this in order to not have to always rely on some premade python library or what have you and actually give a shot at "reinventing the wheel" at some point.

I feel like I understand programming in its most basic, language agnostic functionality (boolean logic, loops, bit operations) but I don't really understand where or how this translates into things like controlling pixels on a screen or rendering 3D objects (since I would have no idea how to create or implement these things from scratch), or more specifically how source code is able to control things like computer memory or write things to storage, or how code is able to interact with the CPU/GPU. Scilicet: I do not quite understand how these basic concepts translate to these impressive higher level representations; I believe this is due to my lack of experience and knowledge of lower-level concepts and theory. Nevertheless, here is my current working knowledge (and please correct me if I am wrong):

>user writes source code to say, draw a line on the screen

>code gets compiled/interpreted down to machine code (in the form of assembly/bytecode/binary)

>OS kernel takes machine code and asks the cpu to allocate memory for this specific task and access to whatever controls the pixels on the display

>machine code executes and display sets pixels (0,0) to (100,100) to blue

I feel like I am missing something here in computer architecture and OS, as I still do not understand how code gets translated and I also suspect my naive interpretation is largely incorrect.

Like , how does the hard drive ( or whatever) literally just forget information?

My both flip-flop(J-K) are repeating or high in the output(Logic high) but it should not have happen.Any solution?I am starter

Guys how would digital security fail if P=NP is proven?

I just started reading about Turing Machine and computational complexity for my Theory of Computation class and came across that phrase.

I couldn't find anything understandable at my level. So can anyone simplify it a bit?

Hey y'all I am interested in learning how to code for scientific and engineering applications and problem solving rather than web or mobile development, how can I start???

I am trying to write a sci-fi thriller where in 2027, there are anomalies in the world which is starting to appear because someone proves P=NP in specific conditions and circumstances and this should have massive consequences, like a ripple effect in the world. I just want to grasp the concept better and understand implications to write this setting better. I was thinking maybe one of the characters "solves" the Hodge conjecture in their dream and claims they could just "see" it ( which btw because a scenario where P=NP is developing) and this causes a domino effect of events.

I want to understand how to "show" Or depict it in fiction, for which I need a better grasp

thanks in advance for helping me out.

What is an efficient way to study and understand a research paper.