How Algorithms Power Computer Programs

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 1.4 Free with a free account

How Algorithms Power Computer Programs

Introduction to Artificial Intelligence · Chapter 1: Foundations of AI and Core ConceptsSection 1.4 · lesson 4 of 6915 min · free with a free account

← Smart Agents and Automated Discovery ToolsNext lesson: Techniques for Computing Logarithmic Values →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

What algorithms are, how to prove them correct, and Big O growth.

  • Define an algorithm and list the five properties it must have
  • Show that an algorithm is correct and terminates using invariants and shrinking quantities
  • Simplify step counts into Big O notation and compare common growth rates
  • Distinguish the search, learning, and optimization families of AI algorithms

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (2,214 words). Read along, or search it.

Opening Question

Behind Every Map and Photo App

Ask a map app for the fastest way home, and in under a second it picks one route out of millions. A photo app finds every picture of your dog. A streaming service lines up a movie you end up loving. None of this is magic, and none of it is guesswork. Behind each result is an algorithm: a precise procedure the computer follows, from the first step to the last. So what exactly is an algorithm? How can we trust one? And how do we know it's fast enough to be useful?

Roadmap

Correctness, Stopping, Growth, and Families

Here's the plan. What an algorithm is. Then, whether it gives the right answer, whether it stops, and how its work grows. And finally, the three families behind most AI.

Definition

A Finite List of Exact Steps

An algorithm is a finite, ordered list of clear steps that takes some input, and produces a desired output. A cooking recipe is the everyday version. The ingredients are the input, the instructions are the steps, and the finished dish is the output. But there's one big difference. A recipe can say, add salt to taste, because a human cook can judge what that means. A computer can't. An algorithm leaves no room for interpretation. Every step is so exact that two different machines, or two different people, would do the same thing.

Algorithm vs Program

One Method, Many Languages

An algorithm is the method. A program is one particular written version of that method, for a specific computer. The same recipe can be printed in English or in Spanish, and still make the same dish. In the same way, one algorithm can be written as a program in many different programming languages.

Worked Example

The Champion Method Finds the Largest

Here's a small algorithm. We want the largest number in the list 4, 9, 2, 7. Step one: look at the first number, and call it the champion. Step two: look at the next number. If it's bigger than the champion, it becomes the new champion. Step three: repeat step two until no numbers are left. Step four: report the champion. Let's trace it. The champion starts as 4, becomes 9, and stays 9 when 2 and 7 are checked. The answer is 9.

Five Properties

What Every Algorithm Needs

Not every list of instructions counts as an algorithm. It needs all five of these properties. Input: zero or more clearly defined values, supplied at the start, like a list of numbers, a map, or an image. Output: at least one result, related to the input. The largest number. The best route. Definiteness: every step has only one possible meaning. Pick a big number, is vague. Pick the larger of two numbers, is definite. Finiteness: the procedure stops after a limited number of steps. Effectiveness: every step is simple enough to actually carry out. List every real number, can't be done. Good algorithms also have generality. The champion method works for a list of four numbers, or four million.

Correctness

Right for Every Valid Input

Now the second question: is it correct? An algorithm is correct if, for every valid input, it gives the right output. Those words, every valid input, matter. Working on a few examples isn't enough. In AI, the unusual case is often exactly the one that causes harm. Take two versions of the champion method. Version A starts with the first number as the champion. Version B starts the champion at 0. On 4, 9, 2, 7, both answer 9. On a list holding just 7, both answer 7. But on minus 8, minus 3, minus 5, version A says minus 3, and version B says 0, which is wrong. Zero is bigger than every number in that list. So passing a few tests is not proof of correctness.

Quick Check

A Smallest-Number Method Starting at 100

Quick check. A new method finds the smallest number in a list. It starts its champion at 100, and swaps in any smaller number it sees. Which of these three lists makes it give a wrong answer? Pause, and decide. List B. Every number is above 100, so nothing ever replaces the starting champion. The method reports 100, a number that isn't even in the list. The negative list feels risky, because negatives broke version B. But here they're all below 100, so the right answer, minus 30, is found. The safe fix is the same as before: start with the first number in the list.

Proof Technique

A Statement True After Every Step

A stronger way to reason about correctness is to find a statement that stays true after every step. For version A, it's this: the champion is the largest of the numbers looked at so far. It's true at the start, since only one number has been seen. It stays true after each step, because a new number either replaces the champion, or is ignored. And at the end, when every number has been seen, it gives the answer.

Edge Cases

Testing Where Algorithms Break

Testing still matters, especially on edge cases: the unusual inputs where algorithms tend to break. Good testers always try an empty list, a list with one item, a list with repeated values, and a list of negative numbers. In AI, correct can mean two different things. Some algorithms guarantee the exact best answer. Others are built to be right most of the time, and are judged by how often they succeed. Knowing which kind you're using is part of using it responsibly.

Termination

A Quantity That Keeps Shrinking

The third question: will it ever stop? An algorithm terminates if it stops after a finite number of steps, for every valid input. An answer that never arrives is as useless as a wrong one. The standard proof is to find a quantity that gets smaller every step, and can't shrink forever. In the champion method, it's the count of numbers still waiting to be looked at. Four, three, two, one, zero. It drops by one each step, and can't go below zero, so the method must stop.

Common Mistake

Subtracting 2 Skips Past Zero

Now a procedure that fails this test. Start with a whole number n. Subtract 2. Repeat until n equals exactly 0. Start at 6, and you get 6, 4, 2, 0. It stops. Start at 7, and you get 7, 5, 3, 1, minus 1, minus 3, and so on. It skips right past zero, and never stops. The fix is a safer stopping rule: repeat until n is 0 or less. Stopping rules matter a lot in AI. Many methods repeat a step again and again, improving a little each time. They need a clear rule, like a maximum number of rounds, or stopping when the improvement becomes tiny.

Complexity

Counting Steps Instead of Seconds

Two algorithms can both be correct, and still be very different in practice. One finishes in a blink. The other takes years. Complexity measures two resources. Time complexity: how many basic steps it takes. Space complexity: how much extra memory it needs while it works. We count steps, not seconds, because seconds depend on the computer. Steps depend only on the algorithm, and on the size of the input, which we call n.

Worked Example

Linear Search Versus Binary Search

Here's an example. You must find one name in a list of n names, already sorted alphabetically. Linear search checks the names one by one, from the start. In the worst case, it checks all n of them. Binary search checks the middle name, and throws away the half that can't contain the target. Then it repeats on the half that's left. With 16 names, four halvings narrow the list to a single name. Sixteen, eight, four, two, one. Each check cuts the list in half.

Scaling Up

About Ten More Checks per Thousandfold Growth

Now scale it up. With a thousand names, linear search may need a thousand checks. Binary search needs at most 10. With a million names, it's a million checks, against 20. With a billion, a billion, against 30. Each time the list gets a thousand times longer, binary search needs only about ten more checks. These are worst cases: the most work the algorithm could ever need. Analysts also talk about the best case and the average case, but the worst case is the safest guarantee.

Space Complexity

Trading Memory for Speed

Now memory. The champion method needs just one extra memory spot, for the champion, however long the list is. Making a sorted copy of the list needs extra memory that grows along with n. Often you can trade one resource for the other. A navigation app could store the best route between every pair of intersections: very fast lookups, but a lot of memory. Or it could work out each route only when you ask: slower, but small.

Big O Notation

Two Rules for Simplifying Step Counts

Counting every step exactly is tiring, and the count changes with every small tweak. Big O notation gives a simpler summary: how the step count grows as n grows. It's usually stated for the worst case, and two rules produce it. Rule one: drop constant multipliers. Five n steps and n steps both grow in a straight line, so both are big O of n. Rule two: keep only the fastest-growing part. A count of n squared, plus 50 n, plus 200, becomes big O of n squared.

Why It Works

The Fastest-Growing Part Takes Over

Why is that fair? Watch the parts as n grows. At n equals 10, the n squared part is only 100 of the 800 steps, about 13 percent. At 100, it's 10,000 of 15,200, or 66 percent. At 1,000, it's a million of about 1.05 million: 95 percent. For large n, the n squared part takes over almost completely.

Growth Patterns

From Constant to Exponential

Here are the most common growth patterns, with the steps each one needs. Constant, big O of one: reading the first item of a list. Always one step. Logarithmic, big O of log n, like binary search. Log base two of n is only about 3, 7 and 10, for 10, 100 and 1,000 items. Linear, big O of n: scanning a list once. Linearithmic, big O of n log n: efficient sorting methods, at 33, 664, and nearly 10,000. Quadratic, big O of n squared: comparing every item with every other item, up to a million steps. And exponential, big O of two to the n: trying every possible subset of the items. At n equals 100, that's about 1.3 times ten to the thirty steps. At a thousand items, it's a number with over three hundred digits. Gentle patterns stay manageable. Exponential growth explodes almost at once.

Real Time

Fractions of a Second to Trillions of Years

What does that mean in real time? Suppose a computer does a billion steps per second, and has a million items to handle. A big O of n log n method needs about 20 million steps: roughly two hundredths of a second. A big O of n squared method needs a trillion steps: about 17 minutes. And a big O of two to the n method, on just 100 items, would need about ten to the thirty steps. That's around 40 trillion years. Choosing the right algorithm is often the difference between an instant answer, and no answer at all.

Quick Check

When n Squared Beats 100 n

Quick check. Method P takes 100 n steps. Method Q takes n squared steps. Your list has just 30 items. Which method finishes first on that list? Pause, and decide. Q finishes first. At 30 items, n squared is 900 steps, while 100 n is 3,000. P is the tempting pick, because big O of n grows more slowly than big O of n squared. But Big O describes growth, not speed on small inputs. P only wins once n passes 100. In the same way, 50 n beats n squared only past 50. Always ask how big your real inputs will be. Big O describes memory too. One extra spot, like the champion, is big O of one space. Copying the whole list is big O of n space.

Three Families

Search, Learning, and Optimization

Almost every AI system is built from three kinds of algorithms. Here, we just meet them. Search looks through a space of possibilities for a sequence of actions that reaches a goal, like the moves that solve a puzzle. Its challenge is size: the possibilities can grow exponentially. Learning doesn't follow rules written by a person. It studies many examples, and adjusts itself to capture their patterns. Its cost grows with the data, and the size of the model. Optimization starts with a candidate solution, and keeps adjusting it to improve a score, like a shorter delivery route. Its risk is settling for an answer that's good, but not the best.

Combined Example

A Delivery Robot Uses All Three

Real systems combine the families. Picture a delivery robot in an office building. It uses search to plan a path, learning to recognize people and obstacles from its camera, and optimization to pick the path that wastes the least battery. And every one of those algorithms must be correct, must stop, and must fit its time and memory budget.

Key Takeaways

Properties, Proofs, and Big O

To sum up. An algorithm is a finite list of precise, doable steps, and it needs all five properties. Correct means right for every valid input. Test the edge cases, and look for a statement that stays true at every step. To show it stops, find a quantity that shrinks every step, and can't shrink forever. Big O keeps only the fastest-growing part of the work. And search, learning and optimization, the families behind most AI, all depend on good complexity.

Reflection

Contacts App Versus Search Engine

Here's something to think about. A phone app searches your 500 contacts. A web search engine looks through tens of billions of pages. For which one would you worry more about the growth rate? And what would you do if the faster algorithm needed more memory than the device has?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About How Algorithms Power Computer Programs

What are the five properties of an algorithm?
An algorithm needs input, output, definiteness, finiteness, and effectiveness. It takes zero or more clearly defined inputs and produces at least one related output. Every step has only one possible meaning, the procedure stops after a limited number of steps, and each step is simple enough to actually carry out. Good algorithms also have generality, so the same method works on a list of four numbers or four million.
How do you prove an algorithm is correct?
A strong method is to find a statement that stays true after every step, often called a loop invariant. For finding the largest number, the invariant is that the champion is the largest number seen so far: true at the start, kept true by each step, and the answer at the end. Passing a few tests is not proof, since a version that starts its champion at 0 fails on an all-negative list.
Why is binary search faster than linear search?
Binary search checks the middle of a sorted list and throws away the half that cannot contain the target, so each check halves what is left. Linear search checks items one by one and may need all n checks. For a million names, linear search may need a million checks while binary search needs at most 20, which is why binary search is big O of log n and linear search is big O of n.
Does a lower Big O mean an algorithm is faster on every input?
No, Big O describes how work grows as the input gets larger, not speed on small inputs. A method taking 100 times n steps is big O of n, and one taking n squared steps is big O of n squared, yet at 30 items the second needs 900 steps while the first needs 3,000. The linear method only wins once n passes 100, so the real size of the input matters.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →